Seminar on Online Algorithms

Haim Kaplan, Spring 2022, Wednesdays 18-20, haimk@tau.ac.il

Room changed to Kaplun 118

We will cover some classical work on online algorithm with emphasis on caching and the primal dual framework. The last few lectures will touch upon some recent work on learning-augmented online algorithms. Two of the main books in this field are the followings:

· Borodin and El-Yaniv [BE], Online Computation and Competitive Analysis, Cambridge University Press, 1998

· Buchbinder and Naor [BN], The Design of Competitive Online Algorithms via a Primal–Dual Approach, Foundation and Trend in Theoretical Computer Science, 2009

Also here is a short survey on the recent field of learning-augmented online algorithms:

· Mitzenmacher, Vassilvitskii, Algorithms with Predictions, 2020

Schedule

1) (Feb 23) An introductory lecture

2) (Mar 2) Sleator and Tarjan, Amortized efficiency of list update and paging rules, CACM, 1985, Chapters 3+2 in [BE], Shachaf Cohen

3) (Mar 9) Competitive Paging Algorithms, Fiat, Karp, Luby, McGeoch, Sleator, Young, 1991, J. of Algorithms, Chapter 4 in [BE], Yuval Stein

4) (Mar 16) Metrical task systems, Chapter 9 in [BE], Daniel Peretz

5) (Mar 23) The k-server problem, Chapter 10 in [BE], Shaun Kotek

6) (Mar 30) The primal dual technique, part 1, Chapters 4+5 in [BN], See also Online Primal-Dual Algorithms for Covering and Packing, Buchbinder and Naor, Math. of OR, 2009, Adi Fine, Omer Abramovich, Zohar Barak

7) (April 6) The primal dual technique, part 2, Chapters 4+5 in [BN], See also Online Primal-Dual Algorithms for Covering and Packing, Buchbinder and Naor, Math. of OR, 2009, Adi Fine, Omer Abramovich, Zohar Barak

8) (April 10) A Primal dual Randomized algorithm for weighted paging, Bansal, Buchbinder, Naor, JACM 2012, also chapter 7 in [BN], Barak Ugav

9) (April 27) Randomized competitive algorithms for generalized caching, Bansal, Buchbinder, Naor, SICOMP 2012, also chapter 7 in [BN], Daniel Agassi

10) (May 11) A randomized primal dual analysis of ranking, Devanur, Jain, Kleinberg, SODA 2013, Oren Levy

11) )May 18) Fair online load balancing, Buchbinder and Naor, Journal of scheduling, 2013, Or Vardi

12) (May 25) Competitive caching with machine learning advice, Lykouris and Vassilvitskii, JACM 2021, Gal Wiernik

13) (June 1) The primal-dual method for learning augmented algorithms, Bamas, Maggiori, Svensson, NeurIPS 2020, Roi Bar On, Tsufit Shua

14) (June 3) Learning augmented weighted paging, Bansal, Coester, Kumar, Purohit, Vee, SODA 2022, Michael Sehaik