CMU-CS-07-157Computer Science Department School of Computer Science, Carnegie Mellon University
CMU-CS-07-157
T.-H. Hubert Chan September 2007 Ph.D. Thesis
Keywords: Approximation algorithms, bounded dimension, metric
spaces, embeddings, spannersThe 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 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 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. 91 pages
| |

Return to:
SCS Technical Report Collection This page maintained by reports@cs.cmu.edu |