Home
The Randomized k-Server Conjecture (Online Algorithms meet Linear Programming), Niv Buchbinder, Microsoft Research
The k-server problem is one of the most central and well studied problems in competitive analysis and is considered by many to be the "holy grail" problem in the field. In the k-server problem, there is a distance function d defined over an n-point metric space and k servers located at the points of the metric space. At each time step, an online algorithm is given a request at one of the points of the metric space, and it is served by moving a server to the requested point. The goal of an online algorithm is to minimize the total sum of the distances traveled by the servers so as to serve a given sequence of requests. The k-server problem captures many online scenarios, and in particular the widely studied paging problem. A twenty year old conjecture states that there exists a k-competitive online algorithm for any metric space. The randomized k-server conjecture states that there exists a randomized O(log k)-competitive algorithm for any metric space. While major progress was made in the past 20 years on the deterministic conjecture, only little is known about the randomized conjecture. We present a very promising primal-dual approach for the design and analysis of online algorithms. We survey recent progress towards settling the k-server conjecture achieved using this new framework. Upcoming TOC seminars and related talks: --------------------------------------------------- 11/4: Niv Buchbinder, Microsoft Research 11/18: Serguei Vassilvitskii, Yahoo Research Mon 11/23 4:15pm: Eddie Farhi physics colloquium 12/2: Emanuele Viola, Northeastern University
| What |
|
|---|---|
| When |
Nov 04, 2009 from 12:00 pm to 01:00 pm |
| Where | Maxwell Dworkin 319 |
| Add event to calendar |
 vCal iCal
|