A polylogarithmic-competitive algorithm for the k-server problem

Abstract

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 Õ(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 [22] whenever n is sub-exponential in k. © 2011 IEEE.