Loading...
Please wait, while we are loading the content...
Similar Documents
Approximation algorithms for low-distortion embeddings into low-dimensional spaces (2005)
| Content Provider | CiteSeerX |
|---|---|
| Author | Gupta, Anupam Sidiropoulos, Anastasios Ravi, R. Dhamdhere, Kedar Rabinovich, Yuri |
| Description | In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), ACM |
| Abstract | 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 prob-lem 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 un-weighted trees. This is the first result of this type. 1 |
| File Format | |
| Publisher Date | 2005-01-01 |
| Access Restriction | Open |
| Subject Keyword | Present Several Approximation Algorithm Low-distortion Embeddings Multiplicative Distortion Two-dimensional Plane Unweighted Graph Un-weighted Tree First Result Metric Space Line Embedding Approximation Algorithm Low-dimensional Space |
| Content Type | Text |
| Resource Type | Proceeding Conference Proceedings |
