Approximation Algorithms for Low-Distortion Embeddings Into Low-Dimensional Spaces
journal contributionposted on 01.05.2001 by Mihai Badiou, Kedar Dhamdhere, Anupam Gupta, Yuri Rabinovich, Harald Racke, Ramamoorthi Ravi, Anistasios Sidiropoulos
Any type of content formally published in an academic journal, usually following a peer-review process.
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.