file.pdf (220.85 kB)

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

Download (220.85 kB)
journal contribution
posted on 01.05.2001 by Mihai Badiou, Kedar Dhamdhere, Anupam Gupta, Yuri Rabinovich, Harald Racke, Ramamoorthi 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.