Local global tradeoffs in metric embeddings

Moses Charikar*, Konstantin Makarychev, Yury Makarychev

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

11 Scopus citations

Abstract

Suppose that every k points in a 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 × log(|X|/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(|X|/k)/ log(1/δ)); and for D = 1, we give a lower bound of Ω(log |X| / (log k+log log |X|)). Our bounds significantly improve on the results of Arora, Lovász, Newman, Rabani, Rabinovich and Vempala, who initiated a study of these questions.

Original languageEnglish (US)
Title of host publicationProceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007
Pages713-723
Number of pages11
DOIs
StatePublished - Dec 1 2007
Event48th Annual Symposium on Foundations of Computer Science, FOCS 2007 - Providence, RI, United States
Duration: Oct 20 2007Oct 23 2007

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428

Other

Other48th Annual Symposium on Foundations of Computer Science, FOCS 2007
Country/TerritoryUnited States
CityProvidence, RI
Period10/20/0710/23/07

ASJC Scopus subject areas

  • Engineering(all)

Cite this