The primal-dual approach for online algorithms (Invited speaker)

Online algorithms deal with settings where the input data arrives over time and the current decision must be made by the algorithm without the knowledge of future input. In the last few years, the online primal-dual approach, pioneered by Buchbinder and Naor [4], has emerged as a very powerful and general method to systematically design and analyze online algorithms. In this talk, I will give an overview of the method and show how it unifies and simplifies various previous results. I will also describe the recent successes of this approach in addressing some classic problems such as weighted paging and the randomized k-server problem [2,1]. Finally, we will also see some recent extensions of the method [3,6,5], beyond the original framework of Buchbinder and Naor [4]. Based on joint works with Niv Buchbinder, Aleksander Madry and Joseph (Seffi) Naor