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

Publikation: Konferenzbeitrag › Papier › Begutachtung

61 Zitate (Scopus)

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.

Originalsprache	Englisch
Seiten	119-128
Seitenumfang	10
Publikationsstatus	Veröffentlicht - 2005
Extern publiziert	Ja
Veranstaltung	Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms - Vancouver, BC, USA/Vereinigte Staaten Dauer: 23 Jan. 2005 → 25 Jan. 2005

Konferenz

Konferenz	Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms
Land/Gebiet	USA/Vereinigte Staaten
Ort	Vancouver, BC
Zeitraum	23/01/05 → 25/01/05

Andere Dateien und Links

Verknüpfung zur Publikation in Scopus

Dieses zitieren

@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 - http://www.scopus.com/inward/record.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

Konferenz

Andere Dateien und Links

Fingerprint

Dieses zitieren