The Taub Faculty of Computer Science Events and Talks

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$.

[This paper won the last FOCS best paper award]