Max Cut and the Smallest Eigenvalue

We describe a new approximation algorithm for Max Cut. Our algorithm runs in \tilde O(n^2)time, where nis the number of vertices, and achieves an approximation ratio of .531 In instances in which an optimal solution cuts a 1-\varepsilonfraction of edges, our algorithm finds a solution that cuts a 1-4\sqrt{\varepsilon} + 8\varepsilon-o(1)fraction of edges. Our main result is a variant of spectral partitioning, which can be...