Approximation algorithms for low-distortion embeddings into low-dimensional spaces

We present several approximation algorithms for the problem of embedding metric spaces into a line, and into the 2-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 Õ(n¹/³) approximation for the case of metrics induced by unweighted trees.