Computer Science Department
School of Computer Science, Carnegie Mellon University
Approximation Algorithms for Metric Embedding Problems
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(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. Elkin et al. .