A $(\log n)^{\Omega(1)}$ Integrality Gap for the Sparsest Cut SDP
Jeff Cheeger, Bruce Kleiner, Assaf Naor · 2009
We show that the Goemans-Linial semidefinite relaxation of the Sparsest Cut problem with general demands has integrality gap (log n)Ω(1). This is achieved by exhibiting n-point metric spaces of negative type whose L1distortion is (log n)Ω(1). Our result is based on quantitative bounds on the rate of degeneration of Lipschitz maps from the Heisenberg group to L1when restricted to cosets of the center.