Optimal Rounding for Sparsest Cut

We prove that the integrality gap of the Goemans–Linial semidefinite program for the Sparsest Cut problem (with general capacities and demands) on inputs of size n≥ 2 is Θ(√logn). We achieve this by establishing the following geometric/structural result. If (M,d) is an n-point metric space of negative type, then for every τ>0 there is a random subset Z of M such that for any pair of points x,y∈ M with d(x,y)≥ τ, the probability that both x∈ Z and d(y,Z)≥ βτ/√1+log(|B(y,κ β τ)|/|B(y,β τ)|) is Ω(1), where 0<β<1<κ are universal constants. The proof relies on a refinement of the Arora–Rao–Vazirani rounding technique.