Euclidean distortion and the Sparsest Cut

Sanjeev Arora; James R. Lee; Assaf Naor

doi:10.1145/1060590.1060673

Euclidean distortion and the Sparsest Cut

Sanjeev Arora, James R. Lee, Assaf Naor

Research output: Contribution to journal › Conference article › peer-review

77 Scopus citations

Abstract

We prove that every n-point metric space of negative type (in particular, every n-point subset of L ₁) embeds into a Euclidean space with distortion O(√log n log log n), a result which is tight up to the O(log log n) factor. As a consequence, we obtain the best known polynomial-time approximation algorithm for the Sparsest Cut problem with general demands. If the demand is supported on a subset of size k, we achieve an approximation ratio of O(√log k log log k).

Original language	English (US)
Pages (from-to)	553-562
Number of pages	10
Journal	Proceedings of the Annual ACM Symposium on Theory of Computing
DOIs	https://doi.org/10.1145/1060590.1060673
State	Published - 2005
Event	13th Color Imaging Conference: Color Science, Systems, Technologies, and Applications - Scottsdale, AZ, United States Duration: Nov 7 2005 → Nov 11 2005

All Science Journal Classification (ASJC) codes

Software

Keywords

Approximation Algorithms
Metric Embeddings
Semidefinite Programming
Sparsest Cut

Access to Document

10.1145/1060590.1060673

Cite this

@article{9debf11c0ae6430d975e3a95cfdcef51,

title = "Euclidean distortion and the Sparsest Cut",

abstract = "We prove that every n-point metric space of negative type (in particular, every n-point subset of L 1) embeds into a Euclidean space with distortion O(√log n log log n), a result which is tight up to the O(log log n) factor. As a consequence, we obtain the best known polynomial-time approximation algorithm for the Sparsest Cut problem with general demands. If the demand is supported on a subset of size k, we achieve an approximation ratio of O(√log k log log k).",

keywords = "Approximation Algorithms, Metric Embeddings, Semidefinite Programming, Sparsest Cut",

author = "Sanjeev Arora and Lee, {James R.} and Assaf Naor",

year = "2005",

doi = "10.1145/1060590.1060673",

language = "English (US)",

pages = "553--562",

journal = "Proceedings of the Annual ACM Symposium on Theory of Computing",

issn = "0737-8017",

publisher = "Association for Computing Machinery (ACM)",

note = "13th Color Imaging Conference: Color Science, Systems, Technologies, and Applications ; Conference date: 07-11-2005 Through 11-11-2005",

}

TY - JOUR

T1 - Euclidean distortion and the Sparsest Cut

AU - Arora, Sanjeev

AU - Lee, James R.

AU - Naor, Assaf

PY - 2005

Y1 - 2005

N2 - We prove that every n-point metric space of negative type (in particular, every n-point subset of L 1) embeds into a Euclidean space with distortion O(√log n log log n), a result which is tight up to the O(log log n) factor. As a consequence, we obtain the best known polynomial-time approximation algorithm for the Sparsest Cut problem with general demands. If the demand is supported on a subset of size k, we achieve an approximation ratio of O(√log k log log k).

AB - We prove that every n-point metric space of negative type (in particular, every n-point subset of L 1) embeds into a Euclidean space with distortion O(√log n log log n), a result which is tight up to the O(log log n) factor. As a consequence, we obtain the best known polynomial-time approximation algorithm for the Sparsest Cut problem with general demands. If the demand is supported on a subset of size k, we achieve an approximation ratio of O(√log k log log k).

KW - Approximation Algorithms

KW - Metric Embeddings

KW - Semidefinite Programming

KW - Sparsest Cut

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

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

U2 - 10.1145/1060590.1060673

DO - 10.1145/1060590.1060673

M3 - Conference article

AN - SCOPUS:34848848456

SN - 0737-8017

SP - 553

EP - 562

JO - Proceedings of the Annual ACM Symposium on Theory of Computing

JF - Proceedings of the Annual ACM Symposium on Theory of Computing

T2 - 13th Color Imaging Conference: Color Science, Systems, Technologies, and Applications

Y2 - 7 November 2005 through 11 November 2005

ER -

Euclidean distortion and the Sparsest Cut

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this