How good is the Goemans-Williamson MAX CUT algorithm?

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$); ...

For MAX SAT, which is a well-known NP-hard problem, many approximation algorithms have been proposed. Two types of best approximation algorithms for MAX SAT were proposed by Asano and Williamson: one with best proven performance guarantee 0.7846 and the ...

We describe a new approximation algorithm for Max Cut. Our algorithm runs in $\tilde O(n^2)$ time, where $n$ is the number of vertices, and achieves an approximation ratio of $.531$. In instances in which an optimal solution cuts a $1-\varepsilon$ fraction ...