Thumbnail
Access Restriction
Open

Author Bădoiu, Mihai ♦ Dhamdhere, Kedar ♦ Gupta, Anupam ♦ Rabinovich, Yuri ♦ Räcke, Harald ♦ Ravi, R. ♦ Sidiropoulos, Anastasios
Source CiteSeerX
Content type Text
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Low-distortion Embeddings ♦ Multiplicative Distortion ♦ Unweighted Graph ♦ Present Several Approximation Algorithm ♦ Two-dimensional Plane ♦ Unweighted Tree ♦ First Result ♦ Metric Space ♦ Line Embedding ♦ Approximation Algorithm ♦ Low-dimensional Space
Description Proceedings of the ACM-SIAM Symposium on Discrete Algorithms
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. 1
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article
Publisher Date 2005-01-01