Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut

Shuchi Chawla; Anupam Gupta; Harald Räcke

Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut

Shuchi Chawla, Anupam Gupta, Harald Räcke

Carnegie Mellon University

Publikation: Konferenzbeitrag › Papier › Begutachtung

38 Zitate (Scopus)

Abstract

In this paper, we study the metrics of negative type, which are metrics (V, d) such that √d is an Euclidean metric; these metrics are thus also known as "l ₂-squared" metrics. We show how to embed n-point negative-type metrics into Euclidean space l ₂ with distortion D = O(log ^3/4 n). This embedding result, in turn, implies an O(log ^3/4 k)-approximation algorithm for the Sparsest Cut problem with non-uniform demands. Another corollary we obtain is that n-point subsets of l ₁ embed into l ₂ with distortion O(log ^3/4 n).

Originalsprache	Englisch
Seiten	102-111
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{368a26aecf764eba873a583b539f0919,

title = "Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut",

abstract = "In this paper, we study the metrics of negative type, which are metrics (V, d) such that √d is an Euclidean metric; these metrics are thus also known as {"}l 2-squared{"} metrics. We show how to embed n-point negative-type metrics into Euclidean space l 2 with distortion D = O(log 3/4 n). This embedding result, in turn, implies an O(log 3/4 k)-approximation algorithm for the Sparsest Cut problem with non-uniform demands. Another corollary we obtain is that n-point subsets of l 1 embed into l 2 with distortion O(log 3/4 n).",

author = "Shuchi Chawla and Anupam Gupta and Harald R{\"a}cke",

year = "2005",

language = "English",

pages = "102--111",

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

}

TY - CONF

T1 - Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut

AU - Chawla, Shuchi

AU - Gupta, Anupam

AU - Räcke, Harald

PY - 2005

Y1 - 2005

N2 - In this paper, we study the metrics of negative type, which are metrics (V, d) such that √d is an Euclidean metric; these metrics are thus also known as "l 2-squared" metrics. We show how to embed n-point negative-type metrics into Euclidean space l 2 with distortion D = O(log 3/4 n). This embedding result, in turn, implies an O(log 3/4 k)-approximation algorithm for the Sparsest Cut problem with non-uniform demands. Another corollary we obtain is that n-point subsets of l 1 embed into l 2 with distortion O(log 3/4 n).

AB - In this paper, we study the metrics of negative type, which are metrics (V, d) such that √d is an Euclidean metric; these metrics are thus also known as "l 2-squared" metrics. We show how to embed n-point negative-type metrics into Euclidean space l 2 with distortion D = O(log 3/4 n). This embedding result, in turn, implies an O(log 3/4 k)-approximation algorithm for the Sparsest Cut problem with non-uniform demands. Another corollary we obtain is that n-point subsets of l 1 embed into l 2 with distortion O(log 3/4 n).

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

M3 - Paper

AN - SCOPUS:20744432321

SP - 102

EP - 111

T2 - Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 23 January 2005 through 25 January 2005

ER -

Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut

Abstract

Konferenz

Andere Dateien und Links

Fingerprint

Dieses zitieren