patternMinor
Definition of “c-competitive” algorithm
Viewed 0 times
definitionalgorithmcompetitive
Problem
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?
Solution
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
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
Context
StackExchange Computer Science Q#24364, answer score: 3
Revisions (0)
No revisions yet.