T.-H. Hubert Chan

Approximation Algorithms for Bounded Dimensional Metric Spaces Degree Type: Ph.D. in Computer Science
Advisor(s): Anupam Gupta
Graduated: December 2007

Abstract:

The study of finite metrics is an important area of research, because of its wide applications to many different problems. The input of many problems (for instance clustering, near-neighbor queries and network routing) naturally involves a set of points on which a distance function has been defined. Hence, one would be motivated to store and process metrics in an efficient manner. The central idea in metric embedding is to represent a metric space by a "simpler" one so that the properties of the original metric space are well preserved.

More formally, given a target class C of metrics, an embedding of a finite metric space M = (V, d) into the class C is a new metric space M′=(V′,d′) such that M′∈C. Most of the work on embeddings has used distortion as the fundamental measure of quality; the distortion of an embedding is the worst multiplicative factor by which distances are increased by the embedding φ. In the theoretical community, the popularity of the notion of distortion has been driven by its applicability to approximation algorithms: if the embedding φ: (V, d) → (V′,d′) has a distortion of D, then the costs of solutions to some optimization problems on (V; d) and those on (V′, d′) can only differ by some function of D; this idea has led to numerous approximation algorithms. Seminal results include the O(log n) distortion embeddings of arbitrary metrics into Euclidean spaces with O(log n) dimensions, and the fact that any metric admits an O(log n) stretch spanner with O(n) edges.

The theoretical results mentioned above are optimal. However, they are pessimistic in the sense that such guarantees hold for any arbitrary metric. It is conceivable that better results can be obtained if the input metrics are "simple". The main theme of this work is to investigate notions of complexity for an abstract metric space and theoretical guarantees for problems in terms of the complexity of the input metric.

One popular notion for measuring the complexity of a metric is the doubling dimension, which restricts the local growth rate of a metric. We show that the results on spanners and embeddings can be improved if the given metrics have bounded doubling dimension. For instance, we give a construction for constant stretch spanners with a linear number of edges. Moreover, such metrics can be embedded into Euclidean space with O(log log n) dimensions and o(log n) distortion.

We also study 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, we 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, we give a sub-exponential time algorithm to solve TSP with approximation ratio arbitrarily close to 1 for such metrics.

Thesis Committee:
Anupam Gupta (Chair)
Avrim Blum
R. Ravi
Kenneth L. Clarkson, (IBM Research, Almaden)

Peter Lee, Head, Computer Science Department
Randy Bryant, Dean, School of Computer Science

Keywords:
Approximation algorithms, bounded dimension, metric spaces, embeddings, spanners