CMU-CS-05-152Computer Science Department School of Computer Science, Carnegie Mellon University
CMU-CS-05-152
Kedar Dhamdhere June 2005 Ph.D. Thesis
CMU-CS-05-152.ps
Keywords: Approximation algorithms, metric embedding, distortion,
line metric, spanning trees
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
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
Finally, we consider the problem of constructing a probabilistic
embedding of a graph into its spanning trees. We give a simple
92 pages
| |

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