The integrality gap of the Goemans--Linial SDP relaxation for Sparsest Cut is at least a constant multiple of $\sqrt{\log n}$

Abstract

We prove that the integrality gap of the Goemans--Linial semidefinite programming relaxation for the Sparsest Cut Problem is $\Omega (\sqrt{\log n})$ on inputs with $n$ vertices.

arXiv commentThis is an extended abstract that announces results whose complete proofs appear in https://arxiv.org/abs/1701.00620 (though a large part of this extended abstract is material that does not appear in https://arxiv.org/abs/1701.00620). It will appear in the proceedings of STOC 2017