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.


  • $\begingroup$ 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? $\endgroup$ Apr 27, 2018 at 0:18
  • $\begingroup$ 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. $\endgroup$
    – Neal Young
    Apr 27, 2018 at 12:12
  • $\begingroup$ similar question here: cstheory.stackexchange.com/questions/18786/… $\endgroup$
    – Neal Young
    Apr 27, 2018 at 14:55


Your Answer

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