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 easier 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 input graph by a simpler graph and solve the problem on the simpler graph.
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.