Local global tradeoffs in metric embeddings

DOI10.1137/070712080MaRDI QIDQ3068641zbMATHOpenAlexFDO

Authors Konstantin Makarychev, Yury 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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Distance in graphs (05C12) Special maps on metric spaces (54E40)

Recommendations

• Local versus global properties of metric spaces
• Improved lower bounds for embeddings into \(L_1\)
• Advances in metric embedding theory
• On distance scales, embeddings, and efficient relaxations of the cut cone
• Advances in metric embedding theory

Cited in

(16)

• Online, Dynamic, and Distributed Embeddings of Approximate Ultrametrics
• On linear and semidefinite programming relaxations for hypergraph matching
• On \(L_1\)-embeddability of unions of \(L_1\)-embeddable metric spaces and of twisted unions of hypercubes
• An introduction to the Ribe program
• Sherali-Adams strikes back
• Polynomial integrality gaps for strong SDP relaxations of densest \(k\)-subgraph
• Local embeddings of metric spaces
• Local embeddings of metric spaces
• Local versus global properties of metric spaces
• From weak to strong linear programming gaps for all constraint satisfaction problems
• A local search algorithm for radius-constrained \(k\)-median
• Approximation Limits of Linear Programs (Beyond Hierarchies)
• Union of Euclidean metric spaces is Euclidean
• Inapproximability for metric embeddings into $\mathbb{R}^{d}$
• Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut
• Sherali-adams strikes back

This page was built for publication: Local global tradeoffs in metric embeddings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3068641)