Material Detail

The Primal-Dual approach for Online Algorithms

The Primal-Dual approach for Online Algorithms

This video was recorded at ALGO Annual Meeting 2012, Ljubljana. Online algorithms deal with settings where the input data arrives over time and the current decision must be made by the algo- rithm without the knowledge of future input. In the last few years, the online primal-dual approach, pioneered by Buchbinder and Naor, 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 uni es and simpli es 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. Finally, we will also see some recent extensions of the method.


  • User Rating
  • Comments
  • Learning Exercises
  • Bookmark Collections
  • Course ePortfolios
  • Accessibility Info

More about this material


Log in to participate in the discussions or sign up if you are not already a MERLOT member.