Skip to main content

Local Versus Global Properties of Metric Spaces

Author(s): Arora, Sanjeev; Lovász, László; Newman, Ilan; Rabani, Yuval; Rabinovich, Yuri; et al

To refer to this page use:
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 $\ell_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.
Publication Date: 2012
Citation: Arora, Sanjeev, László Lovász, Ilan Newman, Yuval Rabani, Yuri Rabinovich, and Santosh Vempala. "Local Versus Global Properties of Metric Spaces." SIAM Journal on Computing 41, no. 1 (2012): pp. 250-271. doi:10.1137/090780304
DOI: 10.1137/090780304
ISSN: 0097-5397
EISSN: 1095-7111
Pages: 250 - 271
Type of Material: Journal Article
Journal/Proceeding Title: SIAM Journal on Computing
Version: Final published version. Article is made available in OAR by the publisher's permission or policy.

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.