Euclidean distortion and the Sparsest Cut

Sanjeev Arora, James R. Lee, Assaf Naor

Research output: Contribution to journalConference article

71 Scopus citations

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

Original languageEnglish (US)
Pages (from-to)553-562
Number of pages10
JournalProceedings of the Annual ACM Symposium on Theory of Computing
DOIs
StatePublished - Dec 1 2005
Event13th Color Imaging Conference: Color Science, Systems, Technologies, and Applications - Scottsdale, AZ, United States
Duration: Nov 7 2005Nov 11 2005

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Approximation Algorithms
  • Metric Embeddings
  • Semidefinite Programming
  • Sparsest Cut

Fingerprint Dive into the research topics of 'Euclidean distortion and the Sparsest Cut'. Together they form a unique fingerprint.

  • Cite this