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

Mihai Bǎdoiu; Kedar Dhamdhere; Anupam Gupta; Yuri Rabinovich; Harald Räcke; R. Ravi; Anastasios Sidiropoulos

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

Mihai Bǎdoiu
, Kedar Dhamdhere
, Anupam Gupta
, Yuri Rabinovich
, Harald Räcke
, R. Ravi
, Anastasios Sidiropoulos

Massachusetts Institute of Technology
Carnegie Mellon University
University of Haifa
Tepper School of Business

Research output: Contribution to conference › Paper › peer-review

62 Scopus citations

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 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 ^1/3) approximation for the case of metrics generated by unweighted trees. This is the first result of this type.

Original language	English
Pages	119-128
Number of pages	10
State	Published - 2005
Externally published	Yes
Event	Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms - Vancouver, BC, United States Duration: 23 Jan 2005 → 25 Jan 2005

Conference

Conference	Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms
Country/Territory	United States
City	Vancouver, BC
Period	23/01/05 → 25/01/05

Cite this

@conference{701f86e6c4794563a19a67a439dba45e,

title = "Approximation algorithms for low-distortion embeddings into low-dimensional spaces",

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 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 1/3) approximation for the case of metrics generated by unweighted trees. This is the first result of this type.",

author = "Mihai Bǎdoiu and Kedar Dhamdhere and Anupam Gupta and Yuri Rabinovich and Harald R{\"a}cke and R. Ravi and Anastasios Sidiropoulos",

year = "2005",

language = "English",

pages = "119--128",

note = "Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms ; Conference date: 23-01-2005 Through 25-01-2005",

}

TY - CONF

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

AU - Bǎdoiu, Mihai

AU - Dhamdhere, Kedar

AU - Gupta, Anupam

AU - Rabinovich, Yuri

AU - Räcke, Harald

AU - Ravi, R.

AU - Sidiropoulos, Anastasios

PY - 2005

Y1 - 2005

N2 - 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 Õ(n 1/3) approximation for the case of metrics generated by unweighted trees. This is the first result of this type.

AB - 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 Õ(n 1/3) approximation for the case of metrics generated by unweighted trees. This is the first result of this type.

UR - https://www.scopus.com/pages/publications/20744450090

M3 - Paper

AN - SCOPUS:20744450090

SP - 119

EP - 128

T2 - Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 23 January 2005 through 25 January 2005

ER -

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

Abstract

Conference

Other files and links

Fingerprint

Cite this