How Good is the Goemans--Williamson MAX CUT Algorithm?
Howard J. Karloff · SIAM Journal on Computing · 1999
The celebrated semidefinite programming algorithm for MAX CUT introduced by Goemans and Williamson was known to have a performance ratio of at least $\alpha=\frac 2 {\pi} \min_{0 < \theta\le \pi} \frac \theta {1-\cos \theta}$ ($0.87856 < \alpha < 0.87857$); the exact performance ratio was unknown. We prove that the performance ratio of their algorithm is exactly $\alpha$. Furthermore, we show that it is impossible to add valid linear constraints to improve the performance ratio.