Theory Day March 2, 2009 - Joseph (seffi) Naor

The Primal-Dual method in Online Computation

Abstract:
A unified approach, based on the primal-dual method, is discussed for a wide range of online covering and packing problems, having various objective functions. This approach has lead to a simple alternative view and analysis of many previously suggested algorithms, as well as new results. In particular, a randomized O(log k)-competitive online algorithm for the weighted paging problem, where there is a (page dependent) weight for fetching each page into the cache, and k is the cache size. The focus of the talk will be on developing the general methodology and the special role of complementary slackness therein.
Based on papers with Nikhil Bansal, Niv Buchbinder and Kamal Jain.