The Randomized k-Server Conjecture (Online Algorithms meet Linear
Programming)
ABSTRACT:
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.
BIO:
Niv Buchbinder is a post-doctoral researcher at Microsoft Research, New
England at Cambridge, MA.
Previously, he was a Ph.D. student in Computer Science at Technion, Israel
Institute of Technology under the supervision of Prof Seffi Naor.
His main research interests are algorithms for combinatorial problems in
offline and online settings. He is also interested in algorithmic game
theory problems.