Kedar Dhamdhere

Approximation Algorithms for Metric Embedding Problems Degree Type: Ph.D. in Computer Science
Advisor(s): Guy Blelloch, R. Ravi
Graduated: August 2005

Abstract:

We initiate the study of metric embedding problems from an approximation point of view. Metric embedding is a map from a guest metric to a host metric. The quality of the embedding is defined in terms of distortion, the ratio by which pairwise distances get skewed in the host metric. While metric embeddings in general have received quite a lot of attention in theory community, most of the results about distortion prove uniform bounds that work for various families of host and guest metric.

In this dissertation, we address the question: how to find the best embedding of the particular input metric into a host metric. We consider the real line as the host metric in our study. We consider the following measures of quality of an embedding: distortion, average distortion and additive distortion. The distortion is the maximum ratio by which a pairwise distance gets stretched in a non-contracting embedding. We give O(√n)-approximation for the distortion of embedding an unweighted graph metric to a line metric. The average distortion is the ratio of average distance in the embedded metric to that in the input metric. We give a 17-approximation for the average distortion when embedding an arbitrary finite metric to a line metric. The additive distortion is the total absolute difference between input and output distances. We provide an O(√log n)-approximation for this objective function. We also show NP-hardness of these problems.

We also consider the problem of linear ordering of a metric, i.e. assigning numbers from 1 through n to the points in the metric, so as to minimize the stretch . The stretch is the maximum pairwise distance in the ordering divided by the distance in the input metric. For this problem, we give O(log³ n)-approximation.

Finally, we consider the problem of constructing a probabilistic embedding of a graph into its spanning trees. We give a simple O(log² n)-approximation algorithm that improves on the algorithm of Elkin et al. Elkin et al. [2005].

Thesis Committee:
R. Ravi (Chair)
Anupam Gupta
Guy Blelloch
Piotr Indyk (MIT )

Jeannette Wing, Head, Computer Science Department
Randy Bryant, Dean, School of Computer Science

Keywords:
Approximation algorithms, metric embedding, distortion, line metric, spanning trees