Approximation Algorithms for Low-Distortion Embeddings Into Low-Dimensional Spaces
Mihai Bâdoiu, Kedar Dhamdhere, Anupam Gupta, Yuri G. Rabinovich, Harald Räcke, R. Ravi, Anastasios Sidiropoulos · 2005
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 O(n approximation for the case of metrics generated by unweighted trees. This is the first result of this type.