Improved Lower Bounds for Embeddings into $L_1$
From MaRDI portal
Publication:3654385
DOI10.1137/060660126zbMath1191.68869OpenAlexW2091399525MaRDI QIDQ3654385
Yuval Rabani, Robert Krauthgamer
Publication date: 6 January 2010
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/060660126
graph partitioningapproximation algorithmsedit distanceintegrality gapsemidefinite programming relaxationmetric embeddingsnegative type metrics
Semidefinite programming (90C22) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items
Sketching and Embedding are Equivalent for Norms, Vertical perimeter versus horizontal perimeter, Negative-type diversities, a multi-dimensional analogue of negative-type metrics, Improved approximation of linear threshold functions, Comparison of Metric Spectral Gaps, Convex Relaxations and Integrality Gaps, The Andoni–Krauthgamer–Razenshteyn Characterization of Sketchable Norms Fails for Sketchable Metrics, On Khot’s unique games conjecture, The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ 1, Concentration on the Boolean hypercube via pathwise stochastic analysis