Local Global Tradeoffs in Metric Embeddings

DOI10.1137/070712080zbMath1206.68138MaRDI QIDQ3068641

Yury Makarychev, Moses Charikar, Konstantin Makarychev

Publication date: 17 January 2011

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/070712080

zbMATH Keywords

metric embeddings; lift and project; global local properties

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C12: Distance in graphs

54E40: Special maps on metric spaces

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68W25: Approximation algorithms

Related Items

Inapproximability for metric embeddings into $\mathbb{R}^{d}$, Online, Dynamic, and Distributed Embeddings of Approximate Ultrametrics