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
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
- On the approximability of digraph ordering
- Title not available (Why is that?)
- 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}$
- Title not available (Why is that?)
- 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
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)