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

Authors:
  • YBYair Bartal
    Yair Bartal
  • ABAvrim Blum
    Avrim Blum
  • CBCarl Burch
    Carl Burch
  • ATAndrew Tomkins
    Andrew Tomkins

Abstract
We present a randomized on-line algorithm for the Metrical Task System problem that achieves a competitive ratio of against an oblivious adversary, on any metric space. This is the first algorithm to achieve a sublinear competitive ratio for all m etric spaces. Our algorithm uses a recent result of Bartal (Bar96) that an arbitrary metric space can b e probabilistically approximated by a set of metric spaces called " -hierarchical well-separated trees" ( -HST's). Indeed, the main technical result of this paper is an -competitive algorithm for -HST spaces. This, combined with the result of (Bar96), yields the general bound. Note that for the -server problem on metric spaces of points our result implies a competitive ratio of .