0
$\begingroup$

Is it possible for an online algorithm to perform better than the optimal solution for the offline version of a problem, and if so, in what circumstances?

Doesn't competitive ratio rely on the fact that online algorithm can only reach at most the same performance as the optimal offline solution ?

$\endgroup$

2 Answers 2

1
$\begingroup$

Say there exists some optimal online algorithm $A$ that is better than any offline algorithm. We can create an offline algorithm $A'$ such that when $A'$ receives the input sequence, it will not perform any preprocessing; instead it will feed each request to $A$ one at a time. This offline algorithm must be optimal, given that $A$ is optimal and better than any other offline algorithm.

With this, the performance of the online can never be better than the optimal offline one.

$\endgroup$
1
$\begingroup$

If you have an online algorithm, you can always execute it offline by feeding the elements one at a time, and there's no loss of efficiency. So offline can beat online, and not conversely.

$\endgroup$

Your Answer

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

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