Reference · 1995
Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
Goemans, M. X., & Williamson, D. P. (1995). Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM, 42(6), 1115–1145.
- Authors
- Michel X. Goemans; David P. Williamson
- Venue
- Journal of the ACM 42(6), 1115–1145
A randomized polynomial-time classical algorithm for MaxCut with expected approximation ratio at least 0.878, via semidefinite programming. Placed next to QAOA so the quantum paper's 0.6924 guarantee on 3-regular graphs is not quoted alone. The guarantees are not identical in scope; both numbers are stated on the QAOA page.
Cited by
Updated 7 Oct 2026.