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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademic


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.
Original languageEnglish
Title of host publicationApproximation and Online Algorithms (10th International Workshop, WAOA 2012, Ljubljana, Slovenia, September 13-14, 2012. Revised Selected Papers)
EditorsT. Erlebach, G. Persiano
Place of PublicationBerlin
ISBN (Print)978-3-642-38015-0
Publication statusPublished - 2013
Event10th International Workshop on Approximation and Online Algorithms (WAOA 2012) - Ljubljana, Slovenia
Duration: 13 Sep 201214 Sep 2012
Conference number: 10

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


Conference10th International Workshop on Approximation and Online Algorithms (WAOA 2012)
Abbreviated titleWOA 2012


Dive into the research topics of 'The primal-dual approach for online algorithms (Invited speaker)'. Together they form a unique fingerprint.

Cite this