Local Global Tradeoffs in Metric Embeddings

DOI10.1137/070712080zbMath1206.68138OpenAlexW2004067661MaRDI QIDQ3068641

Yury Makarychev, Konstantin Makarychev, Moses Charikar

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 embeddingslift and projectglobal local properties

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Special maps on metric spaces (54E40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (14)

Approximation Limits of Linear Programs (Beyond Hierarchies) ⋮ On the approximability of digraph ordering ⋮ An introduction to the Ribe program ⋮ Online, Dynamic, and Distributed Embeddings of Approximate Ultrametrics ⋮ Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut ⋮ On linear and semidefinite programming relaxations for hypergraph matching ⋮ Unnamed Item ⋮ Inapproximability for metric embeddings into $\mathbb{R}^{d}$ ⋮ Local embeddings of metric spaces ⋮ Union of Euclidean Metric Spaces is Euclidean ⋮ Sherali-adams strikes back ⋮ On \(L_1\)-embeddability of unions of \(L_1\)-embeddable metric spaces and of twisted unions of hypercubes ⋮ Unnamed Item ⋮ Unnamed Item

This page was built for publication: Local Global Tradeoffs in Metric Embeddings