Max Cut with Small-Dimensional SDP Solutions
This provides a theoretical improvement over the classical Goemans-Williamson algorithm for Max-Cut in the low-dimensional SDP regime, relevant to optimization and approximation algorithms.
The authors study the Max-Cut SDP relaxation when near-optimal solutions are low-dimensional. They present a polynomial-time rounding algorithm that achieves an approximation ratio of at least α_GW + 2^{-O(d)} for any fixed dimension d, beating the Goemans-Williamson bound.
We study the Max-Cut semidefinite programming (SDP) relaxation in the regime where a near-optimal solution admits a low-dimensional realization. While the Goemans--Williamson hyperplane rounding achieves the worst-case optimal approximation ratio $α_{GW}\approx 0.87856$, it is natural to ask whether one can beat $α_{GW}$ when the SDP solution lives in $\mathbb{R}^d$ for a small dimension $d$. We answer this in the affirmative for every fixed $d$: there is a polynomial-time rounding algorithm that, given a $d$-dimensional feasible solution to the standard Max-Cut SDP strengthened with triangle inequalities, produces a cut of expected value at least $(α_{GW}+2^{-O(d)})$ times the SDP value. Our improvement is driven by a new geometric anti-concentration lemma for signs of low-dimensional Gaussian projections.