Local versus Global Properties of Metric Spaces Extended abstract

Sanjeev Arora; László Lovászt; Ilan Newman; Yuval Rabani; Yuri Rabinovich; Santosh Vempala

doi:10.1145/1109557.1109563

Local versus Global Properties of Metric Spaces Extended abstract

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

Research output: Contribution to conference › Paper › peer-review

11 Scopus citations

Abstract

Motivated by applications in combinatorial optimization, we initiate a study of the extent to which the global properties of a metric space (especially, embeddability in ℓ ₁ with low distortion) are determined by the properties of small subspaces. We note connections to similar issues studied already in Ramsey theory, complexity theory (especially PCPs), and property testing. We prove both upper bounds and lower bounds on the distortion of embedding locally constrained metrics into various target spaces.

Original language	English (US)
Pages	41-50
Number of pages	10
DOIs	https://doi.org/10.1145/1109557.1109563
State	Published - 2006
Event	Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms - Miami, FL, United States Duration: Jan 22 2006 → Jan 24 2006

Other

Other	Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms
Country/Territory	United States
City	Miami, FL
Period	1/22/06 → 1/24/06

All Science Journal Classification (ASJC) codes

Software
General Mathematics

Access to Document

10.1145/1109557.1109563

Cite this

@conference{09f5a2406be44ee4bddf87af8ab5e8cd,

title = "Local versus Global Properties of Metric Spaces Extended abstract",

abstract = "Motivated by applications in combinatorial optimization, we initiate a study of the extent to which the global properties of a metric space (especially, embeddability in ℓ 1 with low distortion) are determined by the properties of small subspaces. We note connections to similar issues studied already in Ramsey theory, complexity theory (especially PCPs), and property testing. We prove both upper bounds and lower bounds on the distortion of embedding locally constrained metrics into various target spaces.",

author = "Sanjeev Arora and L{\'a}szl{\'o} Lov{\'a}szt and Ilan Newman and Yuval Rabani and Yuri Rabinovich and Santosh Vempala",

year = "2006",

doi = "10.1145/1109557.1109563",

language = "English (US)",

pages = "41--50",

note = "Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms ; Conference date: 22-01-2006 Through 24-01-2006",

}

TY - CONF

T1 - Local versus Global Properties of Metric Spaces Extended abstract

AU - Arora, Sanjeev

AU - Lovászt, László

AU - Newman, Ilan

AU - Rabani, Yuval

AU - Rabinovich, Yuri

AU - Vempala, Santosh

PY - 2006

Y1 - 2006

N2 - Motivated by applications in combinatorial optimization, we initiate a study of the extent to which the global properties of a metric space (especially, embeddability in ℓ 1 with low distortion) are determined by the properties of small subspaces. We note connections to similar issues studied already in Ramsey theory, complexity theory (especially PCPs), and property testing. We prove both upper bounds and lower bounds on the distortion of embedding locally constrained metrics into various target spaces.

AB - Motivated by applications in combinatorial optimization, we initiate a study of the extent to which the global properties of a metric space (especially, embeddability in ℓ 1 with low distortion) are determined by the properties of small subspaces. We note connections to similar issues studied already in Ramsey theory, complexity theory (especially PCPs), and property testing. We prove both upper bounds and lower bounds on the distortion of embedding locally constrained metrics into various target spaces.

UR - http://www.scopus.com/inward/record.url?scp=33244474846&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33244474846&partnerID=8YFLogxK

U2 - 10.1145/1109557.1109563

DO - 10.1145/1109557.1109563

M3 - Paper

AN - SCOPUS:33244474846

SP - 41

EP - 50

T2 - Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 22 January 2006 through 24 January 2006

ER -

Local versus Global Properties of Metric Spaces Extended abstract

Abstract

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this