Max Cut and the Smallest Eigenvalue

Luca Trevisan

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…