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

Computer Science

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

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).

Original language	English (US)
Pages	102-111
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{4eec8d24afbe41c183c9027e7f84248a,

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

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

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

Other

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this