Fusible HSTs and the randomized k-server conjecture.

We exhibit an $O((\log k)^6)$-competitive randomized algorithm for the$k$-server problem on any metric space. It is shown that a potential-basedalgorithm for the fractional $k$-server problem on hierarchically separatedtrees (HSTs) with competitive ratio $f(k)$ can be used to obtain a randomizedalgorithm for any metric space with competitive ratio $f(k)^2 O((\log k)^2)$.Employing the $O((\log k)^2)$-competitive algorithm for HSTs from our jointwork with Bubeck, Cohen, Lee, and M\k{a}dry (2017) yields the claimed bound.

The best previous result independent of the geometry of the underlying metricspace is the $2k-1$ competitive ratio established for the deterministic workfunction algorithm by Koutsoupias and Papadimitriou (1995). Even for thespecial case when the underlying metric space is the real line, the best knowncompetitive ratio was $k$. Since deterministic algorithms can do no better than$k$ on any metric space with at least $k+1$ points, this establishes that forevery metric space on which the problem is non-trivial, randomized algorithmsgive an exponential improvement over deterministic algorithms.