Many optimization problems arising in the domain of
network design, communication and transportation etc.
can be defined in terms of some metric space. Often
for such problems, it is easier to give approximation
algorithms with good performance bound for some classes
of "simple" metric spaces. Then, one way to design good
approximation algorithms for general metric spaces is to appoximate
any metric space by a simple metric space and then using
a good approximation algorithm for the simple metric space.
The goal of approximating metric spaces has led to the notion
of graph spanners, having many algorithmic applications.
This paper by Yair Bartal (FOCS 96) provides a novel
technique for the design of good randomized algorithms for
optimization problems on metric spaces. It is shown that any
metric space can be probabilistically approximated by a simple
metric space with at most polylogarithm distortion. This metric
space is simple in being a tree metric and very well suited
for designing divide and conquer algorithms. The technique
presented here has been used for solving at least two long-standing
open problems: polylogarithmic competitive ratios for metrical
task systems in the context of online algorithms and polylogarithmic
approximation ratios for the group Steiner tree problem.