The Primal-Dual approach for Online Algorithms
published: Oct. 2, 2012, recorded: September 2012, views: 5198
Report a problem or upload filesIf you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
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.
Link this pageWould you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !