The integrality gap of the Goemans--Linial SDP relaxation...
Assaf Naor, Robert Young·2017-04-05·via cs.DS updates on arXiv.org
We prove that the integrality gap of the Goemans--Linial semidefinite programming relaxation for the Sparsest Cut Problem is $Ω(\sqrt{\log n})$ on inputs with $n$ vertices.