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

Shuchi Chawla, Anupam Gupta, Harald Räcke

Research output: Contribution to journalArticlepeer-review

Abstract

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

Original languageEnglish (US)
Article number22
JournalACM Transactions on Algorithms
Volume4
Issue number2
DOIs
StatePublished - May 1 2008

Keywords

  • Approximation algorithm
  • Embedding
  • Metrics
  • Negative-type metric
  • Sparsest cut

ASJC Scopus subject areas

  • Mathematics (miscellaneous)

Fingerprint

Dive into the research topics of 'Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut'. Together they form a unique fingerprint.

Cite this