<p>In online-setting, we usually allow exponential time to think and come up with a strategy. On the other hand, in offline-setting, we might care about solving a particular problem optimally, or as good as possible, in polynomial time.</p>

<p>Therefore, there is a chance that for some problems, we can actually come up with a strategy that gives us a competitive ratio that is better than best offline-approximation.</p>

<p>These problems could be crucial to study to obtain some insight understanding on online algorithms. Please let me know if you know of some examples.</p>

<p>Thanks.</p>

CC BY-SA 3.0
2018-04-27T00:18:16.093Z
The online model usually does require a fast 'response' time though, correct? So the exponential precomputation must in some sense depend just on the 'structure' of the problem (e.g. number of elements in the list update problem), not on the requests?
Alex Meiburg
CC BY-SA 3.0
2018-04-27T12:12:26.013Z
https://www.sciencedirect.com/science/article/pii/S0020019012002980 -- Online integer packing with recourse.  If I recall, they give constant-competitive algorithms for some integer linear programs.  The algorithms are online with _recourse_ (they can change a limited number of their decisions retroactively), while the offline problem has no poly-time constant approximation algorithms unless P=NP.
Neal Young
CC BY-SA 3.0
2018-04-27T14:55:20.857Z
similar question here: https://cstheory.stackexchange.com/questions/18786/is-there-an-online-algorithm-for-solving-any-p-complete-problem?rq=1
Neal Young
<approximation-algorithms><online-algorithms>
Is there any online problem that the best known competitive ratio is better than the hardness of approximation (or the best known approximation)?
PattaraS
# Is there any online problem that the best known competitive ratio is better than the hardness of approximation (or the best known approximation)?

(Asked by: username_0 on 2018-04-26)

In online-setting, we usually allow exponential time to think and come up with a strategy. On the other hand, in offline-setting, we might care about solving a particular problem optimally, or as good as possible, in polynomial time.

Therefore, there is a chance that for some problems, we can actually come up with a strategy that gives us a competitive ratio that is better than best offline-approximation.

These problems could be crucial to study to obtain some insight understanding on online algorithms. Please let me know if you know of some examples.

Thanks.

**Tags:** approximation-algorithms, online-algorithms

> **Comments:**
> **username_1**: The online model usually does require a fast 'response' time though, correct? So the exponential precomputation must in some sense depend just on the 'structure' of the problem (e.g. number of elements in the list update problem), not on the requests?  
> **username_2**: https://www.sciencedirect.com/science/article/pii/S0020019012002980 -- Online integer packing with recourse.  If I recall, they give constant-competitive algorithms for some integer linear programs.  The algorithms are online with _recourse_ (they can change a limited number of their decisions retroactively), while the offline problem has no poly-time constant approximation algorithms unless P=NP.  
> **username_2**: similar question here: https://cstheory.stackexchange.com/questions/18786/is-there-an-online-algorithm-for-solving-any-p-complete-problem?rq=1  

---

## 0 answers

