1
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ This is a bizarre statement. $\endgroup$
    – Emil Jeřábek
    Nov 25, 2018 at 17:26
  • 2
    $\begingroup$ It looks like the first version of that statement was added in this diff, which also made other questionable (since rectified) changes. $\endgroup$
    – Yonatan N
    Dec 3, 2018 at 17:32
  • 4
    $\begingroup$ In case somebody gets confused: I have meanwhile changed the offending claim in the Wikipedia article. $\endgroup$
    – Emil Jeřábek
    Dec 3, 2018 at 18:03
  • 1
    $\begingroup$ 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. $\endgroup$
    – Neal Young
    Dec 6, 2018 at 0:17
  • 2
    $\begingroup$ BTW this article is unfortunately quite a mess IMO. The whole paragraph about sorting is misguided: insertion sort is a bad example of what online algorithms are about, which is making irrevocable decisions before all the information is available. The examples of online algorithms are all over the place too. I wish I had some time for an edit, but since the current article is so bad, it would require quite a bit of work. $\endgroup$
    – Sasho Nikolov
    Jan 2, 2019 at 23:52

1 Answer 1

Reset to default
0
$\begingroup$

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.

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

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.