Local global tradeoffs in metric embeddings

DOI10.1137/070712080zbMATH Open1206.68138OpenAlexW2004067661MaRDI QIDQ3068641FDOQ3068641

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

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

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)

Cited In (17)

• Local versus global properties of metric spaces
• Approximation Limits of Linear Programs (Beyond Hierarchies)
• Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut
• Sherali-adams strikes back
• Union of Euclidean metric spaces is Euclidean
• Local embeddings of metric spaces
• Local embeddings of metric spaces
• From weak to strong linear programming gaps for all constraint satisfaction problems
• On the approximability of digraph ordering
• Title not available (Why is that?)
• Online, Dynamic, and Distributed Embeddings of Approximate Ultrametrics
• A local search algorithm for radius-constrained \(k\)-median
• Inapproximability for metric embeddings into $\mathbb{R}^{d}$
• 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
• Polynomial integrality gaps for strong SDP relaxations of densest \(k\)-subgraph

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)