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

Computer Science

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

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 (US)
Pages	119-128
Number of pages	10
State	Published - 2005
Event	Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms - Vancouver, BC, United States Duration: Jan 23 2005 → Jan 25 2005

Other

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

ASJC Scopus subject areas

Software
General Mathematics

Cite this

@conference{ecb9221095bb44c580c28391e8787bc6,

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 (US)",

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 - http://www.scopus.com/inward/record.url?scp=20744450090&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=20744450090&partnerID=8YFLogxK

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

Other

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this