<p>This statement seems false to be because of the notion of <em>competitive ratio</em> 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 <strong>knows</strong> the sequence in advance. In particular, the adversary is solving an offline problem. </p>

<p>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: <a href="https://archive.siam.org/meetings/da18/da18_abstracts.pdf" rel="nofollow noreferrer">https://archive.siam.org/meetings/da18/da18_abstracts.pdf</a>) and search for abstracts that study online algorithms. They all use some type of competitive ratio in their analysis.</p>

CC BY-SA 4.0
2018-12-03T19:14:52.447Z
Why the downvotes?
Sandeep Silwal
CC BY-SA 4.0
2018-12-05T20:01:14.093Z
yeah, you are the only one who has tried to help me so far. Thank you
Gabriel Fair
CC BY-SA 4.0
2018-12-03T15:37:09.480Z
2018-12-03T15:37:09.480Z
Sandeep Silwal
<p>According to the wikipedia page for <a href="https://en.wikipedia.org/wiki/Online_algorithm" rel="nofollow noreferrer">Online algorithms</a>, it states:</p>

<blockquote>
  <p>"Not every online algorithm has an offline counterpart."</p>
</blockquote>

<p>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 <strong>only</strong>?</p>

CC BY-SA 4.0
2018-11-25T17:26:54.810Z
This is a bizarre statement.
Emil Jeřábek
CC BY-SA 4.0
2018-12-03T17:32:59.997Z
It looks like the first version of that statement was added [in this diff](https://en.wikipedia.org/w/index.php?title=Online_algorithm&diff=prev&oldid=641330376), which also made other questionable (since rectified) changes.
Yonatan N
CC BY-SA 4.0
2018-12-03T18:03:46.663Z
In case somebody gets confused: I have meanwhile changed the offending claim in the Wikipedia article.
Emil Jeřábek
CC BY-SA 4.0
2018-12-06T00:17:31.713Z
It's true that [some variants](https://www.ics.uci.edu/~irani/pubs/relratio_wads.pdf) 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
CC BY-SA 4.0
2019-01-02T23:30:39.887Z
I don't think there is much to say here. It seems clear from the diff linked by Yonatan that this is just a non-sense statement inserted by someone who doesn't know what they are talking about.
Sasho Nikolov
CC BY-SA 4.0
2019-01-02T23:52:29.803Z
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.
Sasho Nikolov
<online-algorithms>
Does every online algorithm has an offline counterpart?
Gabriel Fair
# Does every online algorithm has an offline counterpart?

(Asked by: username_0 on 2018-11-24)

According to the wikipedia page for [Online algorithms](https://en.wikipedia.org/wiki/Online_algorithm), 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**?

**Tags:** online-algorithms
> **Comments:**
> **username_1**: This is a bizarre statement.  
> **username_2**: It looks like the first version of that statement was added [in this diff](https://en.wikipedia.org/w/index.php?title=Online_algorithm&diff=prev&oldid=641330376), which also made other questionable (since rectified) changes.  
> **username_1**: In case somebody gets confused: I have meanwhile changed the offending claim in the Wikipedia article.  
> **username_3**: It's true that [some variants](https://www.ics.uci.edu/~irani/pubs/relratio_wads.pdf) 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.  
> **username_4**: I don't think there is much to say here. It seems clear from the diff linked by Yonatan that this is just a non-sense statement inserted by someone who doesn't know what they are talking about.  
> **username_4**: 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.  

---

## 1 answers

### Answer by username_5 on 2018-12-03. Score: 0 | Accepted answer

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.

> **Comments:**
> **username_5**: Why the downvotes?  
> **username_0**: yeah, you are the only one who has tried to help me so far. Thank you  

---

