0
$\begingroup$

When defining an online algorithm, it is common to assume that there exists an optimal offline algorithm to be used over the set of already known requests.

For example, consider the IGNORE algorithm for the online TSP problem. When the first request appears, go visit that point. Ignore any requests that may appear on the way. When you arrive at the first point, compute an optimal tour serving all currently unserved points. Repeat.

This algorithm assumes that we can compute the optimal tour over the set of unserved requests. But since TSP is NP Hard, we may want to use an approximation algorithm for this. So one could define a modified version of IGNORE, where, a tour serving all unserved points is computed with some approximation algorithm (for example Christofides' algorithm, which is $\frac{3}{2}$-approximative).

My question is the following: how would this affect the competitive ratio of the algorithm? If we consider an online algorithm ALG that is $c$-competitive, and modify it as above to include an $\alpha$-approximation algorithm, is the resulting algorithm $c \cdot \alpha$-competitive? If so, why?

The trick, I think, is to answer the question, if the modified online algorithm is an $\alpha$-approximation of the original online algorithm. Does that always have to be the case?

Improve this question
$\endgroup$
1
  • $\begingroup$ I think this would depend on the details of how the $c$-competitive ratio is proved. It seems likely to often be true that the competitive ratio degrades nicely like that, but probably there exists some counterexample where the online algorithm uses the offline solution in some clever way and/or local errors can compound badly. $\endgroup$
    – usul
    Jul 21 at 21:57

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.