May 15, Tuesday
12:00 – 13:00
A Polylogarithmic-Competitive Algorithm for the k-Server Problem
Computer Science seminar
Lecturer : Niv Buchbinder
Affiliation : Department of Mathematics and Computer Science , Open university
Location : 202/37
Host : Dr. Aryeh Kontorovich
The k-server problem is one of the most fundamental and extensively
studied problems in online computation. Suppose there is an n-point
metric space and k servers are located at some of 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 this request is
served by moving a server to the requested point (if there is no
server there already). The cost of serving a request is defined to be
the distance traveled by the server. Given a sequence of requests, the
task is to devise an online strategy minimizing the sum of the costs of serving the requests.
We give the first polylogarithmic-competitive randomized online
algorithm for the k-server problem on an arbitrary finite metric
space. In particular, our algorithm achieves a competitive ratio of
O(log^3 n log^2 k) for any metric space on n points. Our algorithm
improves upon the deterministic (2k-1)-competitive algorithm of
Koutsoupias and Papadimitriou whenever n is sub-exponential in k.
Joint with Nikhil Bansal, Aleksander Madry and Seffi Naor