January 13, Wednesday 14:15, Room 303, Jacobs Building
The Randomized k-Server Conjecture (Online
Algorithms meet Linear Programming)
Lecturer : Niv Buchbinder
Lecturer homepage : http://research.microsoft.com/en-us/um/people/nivbuchb/
Affiliation : 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.