3
$\begingroup$

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?

$\endgroup$
1
3
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$ May 3 '14 at 20:34
  • $\begingroup$ @DavidRicherby What about F is a feasible solution on input I? $\endgroup$ May 3 '14 at 22:06
  • 1
    $\begingroup$ @FilipeGonçalves So what does $O\in F(I)$ mean? $\endgroup$ May 3 '14 at 22:45
  • $\begingroup$ $O\in F(I)$ is a output of set of feasible solutions on input $I$ $\endgroup$ May 4 '14 at 9:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.