Fusible HSTs and the Randomized k-Server Conjecture

We exhibit a poly(log k)-competitive randomized algorithm for the k-server problem on any metric space. 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. Our algorithm maintains an approximation of the underlying metric space by a distribution over HSTs. The granularity and accuracy of the approximation is adjusted dynamically according to the aggregate behavior of the HST algorithms. In short: We try to obtain more accurate approximations at the locations and scales where the "gaction" is happening. Thus a crucial component of our approach is the O((log k)
²
)-competitive randomized algorithm for HSTs obtained in our previous work with Bubeck, Cohen, Lee, and Ma.dry, and its "multiscale information theory" perspective.