Are there any recent books on Online Algorithms? I know of only two books on the subject.

  • Online Computation and Competitive Analysis by Allan Borodin and Ran El-Yaniv: This is a classic but old book, and does not contain many recent advances in the field.
  • The Design of Competitive Online Algorithms via a Primal-Dual Approach by Niv Buchbinder and Joseph (Seffi) Naor: This is a new book and contains lot of recent results. However, it's scope is limited to LP based primal-dual algorithms.

Please list here all the books on Online Algorithms that you may know. If there are any books freely available on the web, that will be great.

  • 2
    $\begingroup$ Sounds like a CW questions ? definitely a big-list $\endgroup$ – Suresh Venkat Dec 3 '12 at 4:52
  • $\begingroup$ have noticed on tcs.se over ~1yr a seeming uptick in interest in online algorithms for eg misc std graph problems, seems to tie in with trends around "big data" (& cloud algorithms etc). & it would seem there are not great refs on the subj so far, the coverage seems more scattered right now... in many cases taking efficient offline algorithms & making/adapting them to online scenarios is an extremely nontrivial/advanced area... maybe early signs of a paradigm shift in progress? $\endgroup$ – vzn Dec 3 '12 at 18:48

It seems that there are no recent books or survey papers on online algorithms.


This might be of some relevance http://www.cs.cmu.edu/~arielpro/15896s15/docs/paper13b.pdf Survey by Aranyak Mehta (Google Research)

  • 1
    $\begingroup$ Title for the lazy: "Online Matching and Ad Allocation" $\endgroup$ – Neal Young Sep 9 '19 at 7:27

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.