| The goal of approximating metric spaces by more simple
metric spaces has led to the notion of graph spanners [PU89,
PS89] and to low-distortion embeddings in low-dimensional spaces
[LLR94], having many algorithmic applications.
This paper provides a novel technique for the analysis of randomized
algorithms for optimization problems on metric spaces, by relating
the randomized performance ratio for any metric space to the
randomized performance ratio for a set of "simple" metric spaces.
We define a notion of a set of metric spaces that
probabilistically-approximates another metric space. We prove that
any metric space can be probabilistically-approximated by hierarchically
well-separated trees (HST) with a polylogarithmic distortion. These
metric spaces are "simple" as being: (1) tree metrics. (2) natural
for applying a divide-and-conquer algorithmic approach.
The technique presented is of particular interest in the context
of on-line computation. A large number of on-line algorithmic
problems, including metrical task systems [BLS87], server problems
[MMS88] , distributed paging [BFR92], and dynamic storage rearrangement
[FMRW95], are defined in terms of some metric space. Typically for
these problems, there are linear lower bounds on the competitive
ratio of deterministic algorithms. Although randomization against
an oblivious adversary has the potential of overcoming these high
ratios, very little progress has been made in the analysis.
We demonstrate the use of our technique by obtaining substantially
improved results for two different on-line problems. For metrical
task systems [BLS87] we give first sub-linear randomized competitive
ratio for a large set of metric spaces. For constrained file migration
[BFR92] we give first randomized algorithms for general networks
with polylogarithmic competitive ratio.
|