# Definition of “c-competitive” algorithm

What is the definition of a "c-competitive" algorithm? For example what does it mean, if we say that there is a 2-competitive algorithm for packet routing?

You are given algorithm $ALG$ for optimization problem $\mathcal{P}$ and and cost function $\mathcal C$.

You can define cost of optimal algorithm $OPT$ as:

$C(OPT(I))=\min_{O\in F(I)}\mathcal C(I,O)$, where $I$ is valid input, $F$ is a feasible solution on input $I$ and $O$ is the output associated with that feasible solution. Then you can define cost of c-competitive algorithm as:

$\mathcal C(ALG(I))\le c\cdot \mathcal C(OPT(I)) + \alpha$,

Where $\alpha$ arbitrary is constant, if $\alpha = 0$ then we are talking about strictly c-competitive algorithm

• I corrected some typos in this but there's a little more still to do. You don't define what $F(I)$ is, for example. May 3 '14 at 20:34
• @DavidRicherby What about F is a feasible solution on input I? May 3 '14 at 22:06
• @FilipeGonçalves So what does $O\in F(I)$ mean? May 3 '14 at 22:45
• $O\in F(I)$ is a output of set of feasible solutions on input $I$ May 4 '14 at 9:57