Kunal Talwar (University of California, Berkeley):
Approximating metrics by simpler metrics: Why and how?
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.