Local versus global properties of metric spaces

Sanjeev Arora, László Lovász, Ilan Newman, Yuval Rabani, Yuri Rabinovich, Santosh Vempala

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

Abstract

Motivated by applications in combinatorial optimization, we study the extent to which the global properties of a metric space, and especially its embeddability into 1 with low distortion, are determined by the properties of its small subspaces. We establish both upper and lower bounds on the distortion of embedding locally constrained metrics into various target spaces. Other aspects of locally constrained metrics are studied as well, in particular, how far are those metrics from general metrics.

Original languageEnglish (US)
Pages (from-to)250-271
Number of pages22
JournalSIAM Journal on Computing
Volume41
Issue number1
DOIs
StatePublished - Jun 4 2012

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Keywords

  • Dimension-reduction
  • Sparsification

Fingerprint Dive into the research topics of 'Local versus global properties of metric spaces'. Together they form a unique fingerprint.

Cite this