Title: Fusible HSTs and the randomized k-server conjecture,
Abstract: 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-based
algorithm for the fractional $k$-server problem on hierarchically separated
trees (HSTs) with competitive ratio $f(k)$ can be used to obtain a randomized
algorithm 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 joint
work with Bubeck, Cohen, Lee, and Mądry (2017) yields the claimed bound.
The best previous result independent of the geometry of the underlying metric
space is the $2k-1$ competitive ratio established for the deterministic work
function algorithm by Koutsoupias and Papadimitriou (1995). Even for the
special case when the underlying metric space is the real line, the best known
competitive 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 for
every metric space on which the problem is non-trivial, randomized algorithms
give an exponential improvement over deterministic algorithms.