Kedar Dhamdhere
Computer Science Department
Date: Friday, June 24, 2005
Time: 2 pm
Place: Wean 4623
Title: Approximation Algorithms for Metric Embedding Problems
Abstract:
We initiate the study of metric embedding problems from approximation point
of view. Metric embedding is a map from the guest metric to the 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 the 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(sqrt{n})-approximation for the distortion of embedding
an unweighted graph metric to the 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(sqrt{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(log3 n)-approximation.
Finally, we consider the problem of constructing a probabilistic embedding of
a graph into its spanning trees. We give a simple O(log2 n)-approximation
algorithm that improves on the algorithm of Elkin et al.
Thesis Committee:
R. Ravi, Chair
Anupam Gupta
Guy Blelloch
Piotr Indyk, MIT
Thesis summary available at: http://www.cs.cmu.edu/~kedar/thesis.html
