A Polylogarithmic-Competitive Algorithm for the k-Server Problem
Nikhil Bansal, Niv Buchbinder, Aleksander Mądry, Joseph Seffi Naor · 2011
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 Õ(log3n log2k) for any metric space on n points. This improves upon the (2k-1)-competitive algorithm of Koutsoupias and Papadimitriou (J. ACM 1995) whenever n is sub-exponential in k.