Local global tradeoffs in metric embeddings

Moses Charikar*, Konstantin Makarychev, Yury Makarychev

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

12 Scopus citations

Abstract

Suppose that every k points in a n point metric space X are D-distortion embeddable into ℓ1. We give upper and lower bounds on the distortion required to embed the entire space X into ℓ1. This is a natural mathematical question and is also motivated by the study of relaxations obtained by lift-and-project methods for graph partitioning problems. In this setting, we show that X can be embedded into ℓ1 with distortion O(D X log(n/k)). Moreover, we give a lower bound showing that this result is tight if D is bounded away from 1. For D = 1 + δ we give a lower bound of ω(log(n/k)/log(1/δ)); and for D =1, we give a lower bound of ω(logn/(log k + loglogn)). Our bounds significantly improve on the results of Arora et al. who initiated a study of these questions.

Original languageEnglish (US)
Pages (from-to)2487-2512
Number of pages26
JournalSIAM Journal on Computing
Volume39
Issue number6
DOIs
StatePublished - May 19 2010

Keywords

  • Global local properties
  • Lift and project
  • Metric embeddings

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Local global tradeoffs in metric embeddings'. Together they form a unique fingerprint.

Cite this