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

Yair Bartal, Avrim Blum, Carl Burch, and Andrew Tomkins

extended abstract,
(ps.gz, PDF)
STOC '97, pp 711-719,
© 1997, by ACM, Inc

journal version
(ps.gz, PDF)
(submitted)

### 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`).

A polylog(n)-competitive algorithm for metrical task systems /
Publications /
Carl Burch