The traveling salesman problem is NP-hard, as are several other
optimization problems such as group steiner tree and k-server. On the
other hand, many such problems are easy to solve when the underlying
graph is simple, say a tree. A natural approach to get approximately
optimal solutions for the above problems is to approximate the
shortest path metric on the input graph by a simpler metric and
solve the problem on the resulting instance.

We show how to approximate any graph metric by a distribution over
trees, such that internode distances are preserved upto a logarithmic
factor (in expectation). This settles a long open question and gives
simpler and improved approximation algorithms for several problems. We
also show how our techniques lead to a quasi-polynomial approximation
scheme for the traveling salesman problem on low-dimensional metrics.