Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.


We give the first polylogarithmic-competitive randomized algorithm for the $k$-server problem on an arbitrary finite metric space. In particular, our algorithm achieves a competitive ratio of $\widetilde{O}(\log^3 n \log^2 k)$ for any metric space on $n$ points. This improves upon the $(2k-1)$-competitive algorithm of Koutsoupias and Papadimitriou (J.ACM.'95) whenever $n$ is sub-exponential in $k$.

Questions and Answers

You need to be logged in to be able to post here.