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

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

40 Scopus citations

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
Pages	102-111
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{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 - https://www.scopus.com/pages/publications/20744432321

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

Conference

Other files and links

Fingerprint

Cite this