A $(\log n)^{\Omega(1)}$ Integrality Gap for the Sparsest Cut SDP

DOI10.1109/FOCS.2009.47zbMath1291.90318arXiv0910.2024MaRDI QIDQ5171219

Jeff Cheeger, Assaf Naor, Bruce Kleiner

Publication date: 25 July 2014

Published in: 2009 50th Annual IEEE Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0910.2024

Mathematics Subject Classification ID

Semidefinite programming (90C22) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Related Items

Vertical perimeter versus horizontal perimeter, Realization of metric spaces as inverse limits, and bilipschitz embedding in \(L_1\), Sharp quantitative nonembeddability of the Heisenberg group into superreflexive Banach spaces, Metric differentiation, monotonicity and maps to \(L^{1}\), Compression bounds for Lipschitz maps from the Heisenberg group to \(L_{1}\), Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack, Heat flow and quantitative differentiation, Inverse limit spaces satisfying a Poincaré inequality, Convex Relaxations and Integrality Gaps, Strong reductions for extended formulations, On Khot’s unique games conjecture, The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ ₁, Superlinear Integrality Gaps for the Minimum Majority Problem, Low dimensional embeddings of doubling metrics