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_{Oin 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 ccdot 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
