A polylog(n)-competitive algorithm for metrical task systems

Abstract

We present a randomized on-line algorithm for the Metrical Task System problem that achieves a competitive ratio of O(log^6 n) for arbitrary metric spaces, against an oblivious adversary. This is the first algorithm to achieve a sublinear competitive ratio for all metric spaces. Our algorithm uses a recent result of Bartal [Bartal96] that an arbitrary metric space can be probabilistically approximated by a set of metric spaces called ``k-hierarchically well-separated trees'' (k-HST's). Indeed, the main technical result of this paper is an O(log^2 n)-competitive algorithm for Omega(log^2 n)-HST spaces. This, combined with the result of [Bartal96], yields the general bound.

Note that for the k-server problem on metric spaces of k+c points our result implies a competitive ratio of O(c^6 log^6 k).