Metric methods in approximation algorithms

In recent years we have witnessed a fascinating and fruitful confluence of the theory of metric spaces and theoretical computer science. The results of this thesis lie in this intersection.; In the first part of the thesis, we look at the problem of embedding metrics into a linear combination of trees. Improving on a result of Bartal, we show that any metric embeds into a distribution over dominating tree metrics with distortion at most O(log n). Our distortion bound matches the known lower bound and settles a decade old question. It leads to improved approximation and online algorithms for numerous problems and gives an alternate proof of Bourgain's theorem for ℓ1. Our techniques also settle the question of the performance of divide-and-conquer type approximation algorithms. As a result, we get improved approximation algorithms for yet more problems.; The second part of the thesis studies a natural notion of the dimension of an abstract metric space. Ideally, we would have liked to embed low dimensional abstract metric spaces into a low dimensional normed space, so as to the exploit the well studied algorithmic and structural properties of Euclidean and other normed spaces. While that may be difficult, we show how to bypass the embedding for several applications by generalizing several results for low dimensional Euclidean metrics to low dimensional abstract metrics. In particular, we show that low dimensional abstract spaces admit quasipolynomial time approximation schemes for several optimization problems including the traveling salesman problem. We also show that such metrics have short distance labels, compact routing schemes and small spanners.