2
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.