Local global tradeoffs in metric embeddings

DOI10.1137/070712080MaRDI QIDQ3068641zbMATH OpenOpenAlexFDO

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

global local propertieslift and projectmetric embeddings

Mathematics Subject Classification ID

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

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

(18)

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

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)