Rounding guarantees for low-dimensional Max-Cut semidefinite relaxations
Follow the latest progress by email.
Given a feasible d-dimensional Max-Cut semidefinite solution strengthened by triangle inequalities, can polynomial-time rounding beat α_GW by 2^−O(d)?
Why it matters and what counts as progress
Why it matters: It asks for a dimension-sensitive improvement over the usual rounding ratio while retaining the stronger relaxation’s constraints.
What counts as progress: A provable improvement above α_GW for every fixed SDP dimension, or sharper dimension dependence under the same triangle inequalities.
How the problem developed
- 1995 · Algorithm [1]
Michel X. Goemans and David P. Williamson Introduced randomized hyperplane rounding with the general Max-Cut guarantee α_GW≈0.87856.
- 2005 · Partial result [2]
Yair Avidor and Uri Zwick Improved rounding guarantees for two- and three-dimensional SDP solutions and posed the fixed higher-dimensional case.
- 15 Apr 2026 · Algorithm [3]
Xiaoyu Chang, Niladri Ghoshal and James R. Lee For every fixed dimension d, gave randomized polynomial-time rounding for feasible d-dimensional Max-Cut SDP solutions with triangle inequalities, improving the Goemans–Williamson factor by 2⁻ᴼ⁽ᵈ⁾.
AI contribution
Max Cut with Small-Dimensional SDP Solutions
For a feasible d-dimensional Max-Cut SDP solution strengthened by triangle inequalities, a randomized polynomial-time rounding algorithm attains expected cut value at least (α_GW+2^(−O(d))) times the SDP value.
Sources
- Goemans and Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Avidor and Zwick, Approximating MAX CUT with a fixed number of spins
- Chang, Ghoshal and Lee, Max Cut with Small-Dimensional SDP Solutions
- Max Cut with Small-Dimensional SDP Solutions
Website timeline
Publication dates and editorial changes.
Model-assisted lemma improves low-dimensional Max-Cut rounding