Carnegie Mellon University
file.pdf (220.85 kB)

Approximation Algorithms for Low-Distortion Embeddings Into Low-Dimensional Spaces

Download (220.85 kB)
journal contribution
posted on 2001-05-01, 00:00 authored by Mihai Badiou, Kedar Dhamdhere, Anupam Gupta, Yuri Rabinovich, Harald Racke, Ramamoorthi RaviRamamoorthi Ravi, Anistasios Sidiropoulos
We present several approximation algorithms for the problem of embedding metric spaces into a line, and into the two-dimensional plane. Among other results, we give an O(√n)-approximation algorithm for the problem of finding a line embedding of a metric induced by a given unweighted graph, that minimizes the (standard) multiplicative distortion. We give an improved Õ(n1/3) approximation for the case of metrics generated by unweighted trees. This is the first result of this type.




Usage metrics