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 𝑛 ⩾ 2 is Θ( √︁ log 𝑛). We achieve this by establishing the following geometric/structural result. If (M, 𝑑) is an 𝑛-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 𝑥, 𝑦 ∈ M with 𝑑 (𝑥, 𝑦) ⩾ 𝜏, the probability that both 𝑥 ∈ Z and 𝑑 (𝑦, Z) ⩾ 𝛽𝜏/ √︁ 1 + log(|𝐵(𝑦, 𝜅𝛽𝜏)|/|𝐵(𝑦, 𝛽𝜏)|) is Ω(1), where 0 < 𝛽 < 1 < 𝜅 are universal constants. The proof relies on a refinement of the Arora-Rao-Vazirani rounding technique.