A polylog( n )-competitive algorithm for metrical task systems
Yair Bartal, Avrim L. Blum, Carl Burch, Andrew Tomkins · 1997
We present a randomized on-line algorithm for the Metrical Tti System problem that achieves a competitive ratio of O(log6 n) for arbitrary metric spaces, against art oblivious adversary.This is the first algorithm to achieve a sublinear competitive ratio for all mernc spaces.Our algorithm uses a recent result of Bart.al[Bar96] thatan arbitrarymetric space can be probabilistically approximated by a set of metric spaces called "k-hierarchical well-separated trees" (k-HST'S).Indeed, the main technical result of this paper is an 0(}og2 n)-competitive algorithm for fl(log2 n)-HST spaces.This, combined with the result of [Bar96], 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(C6 log6 k).