[Solved]: Definition of “c-competitive” algorithm

Problem Detail: 

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?

Asked By : George Ts

Answered By : Bartosz Przybylski

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/24364