Fréchet embeddings of negative type metrics

Sanjeev Arora, James R. Lee, Assaf Naor

Research output: Contribution to journalArticle

Abstract

We show that every n-point metric of negative type (in particular, every n-point subset of L 1) admits a Fréchet embedding into Euclidean space with distortion O(√log n · log log n), a result which is tight up to the O(log∈log∈n) factor, even for Euclidean metrics. This strengthens our recent work on the Euclidean distortion of metrics of negative into Euclidean space.

Original languageEnglish (US)
Pages (from-to)726-739
Number of pages14
JournalDiscrete and Computational Geometry
Volume38
Issue number4
DOIs
StatePublished - Dec 2007

Keywords

  • Distortion
  • Euclidean
  • L
  • Metric embeddings
  • Sparsest cut problem

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Fréchet embeddings of negative type metrics'. Together they form a unique fingerprint.

  • Cite this