According to the wikipedia page for Online algorithms, it states:

"Not every online algorithm has an offline counterpart."

At the time of asking this question there is no citation for this claim. How it possible to not have an offline counterpart? What is an example of an algorithm that is online only?

  • 1
    This is a bizarre statement. – Emil Jeřábek Nov 25 at 17:26
  • 1
    It looks like the first version of that statement was added in this diff, which also made other questionable (since rectified) changes. – Yonatan N Dec 3 at 17:32
  • 2
    In case somebody gets confused: I have meanwhile changed the offending claim in the Wikipedia article. – Emil Jeřábek Dec 3 at 18:03
  • It's true that some variants of competitive analysis compare online algorithms directly, without reference to the offline optimum, but that's not what's being asserted apparently. One could certainly define online games that don't terminate, and so in some sense have no "offline" algorithms at all. I guess the assertion as given is not sufficiently well defined to be falsifiable. – Neal Young Dec 6 at 0:17

This statement seems false to be because of the notion of competitive ratio that is used to analyze virtually all online algorithms. Heuristically the competitive ratio measures how well the online algorithm performs on a sequence of inputs versus an adversary that knows the sequence in advance. In particular, the adversary is solving an offline problem.

If you look at any of the online problems that are studied, they all use the competitive ratio as a benchmark. To back up this claim, look at the abstracts of any paper in a well known journal (such as SODA 18: https://archive.siam.org/meetings/da18/da18_abstracts.pdf) and search for abstracts that study online algorithms. They all use some type of competitive ratio in their analysis.

  • 1
    Why the downvotes? – Sandeep Silwal Dec 3 at 19:14
  • yeah, you are the only one who has tried to help me so far. Thank you – Gabriel Fair Dec 5 at 20:01

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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