Approximation Algorithms for Bounded Dimensional Metric Spaces

One popular notion for measuring the complexity of a metric is the doubling dimension, which restricts the local growth rate of a metric. My work considers two problems on doubling metrics: sparse spanners and Euclidean embeddings. For doubling metrics, one can construct constant stretch spanners with linear number of edges, while a sparse spanner for a general metric can incur a stretch at least Omega(log n). One can embed doubling metrics into Euclidean space with O(log log n) dimensions and o(log n) distortion, while a general metric space can take at least Omega(log n/ log log n) dimensions even if distortion O(log n) is allowed.

My work also considers a new notion of dimension that captures the global growth rate of a metric. Such a notion strictly generalizes doubling dimension in the sense that it places weaker restrictions on a given metric than those posed by doubling dimension. However, one can still obtain good guarantees for problems in which the objective depends on the global nature of the metric, an example of which is the Traveling Salesperson Problem (TSP). In particular, a sub-exponential time algorithm is given to solve TSP with approximation ratio arbitrarily close to 1 for such metrics.