Online Algorithms and the k-server Conjecture
Speaker: Aleksander Madry , Microsoft Research-New England
Date: November 22 2011
Time: 4:15PM to 5:15PM
Location: 32-124
Host: Dana Moshkovitz and Costis Daskalakis, CSAIL, MIT
Contact: Be Blackburn, 3-6098, imbe@mit.edu
Traditionally, in the problems considered in optimization, one needs to produce the solution only after the whole input is made available. However, in many real-world scenarios the input is revealed gradually, and one needs to make irrevocable decisions along the way while having only partial information on the whole input. This motivates us to develop models that allow us to address such scenarios.
In this talk, I will consider one of the most popular approaches to dealing with uncertainty in optimization: the online model and competitive analysis; and focus on a central problem in this area: the k-server problem. This problem captures many online scenarios - in particular, the widely studied caching problem - and is considered by many to be the "holy grail" problem of the field. I will present a new randomized algorithm for the k-server problem that is the first online algorithm for this problem that achieves polylogarithmic competitiveness.
Based on joint work with Nikhil Bansal, Niv Buchbinder, and Joseph (Seffi) Naor.
See other events that are part of Theory Colloquium 2011/2012
See other events happening in November 2011
