Max Cut and the smallest eigenvalue

We describe a new approximation algorithm for Max Cut. Our algorithm runs in O~(n2) time, where n is the number of vertices, and achieves an approximation ratio of .531. On instances in which an optimal solution cuts a 1−ϵ fraction of edges, our algorithm finds a solution that cuts a 1−4ϵ√+8ϵ−o(1) fraction of edges. Our main result is a variant of spectral partitioning, which can be implemented in nearly linear time. Given a graph in which the Max Cut optimum is a 1−ϵ fraction of edges, our spectral partitioning algorithm finds a set S of vertices and a bipartition L,R=S−L of S such that at least a 1−O(ϵ√) fraction of the edges incident on S have one endpoint in L and one endpoint in R. (This can be seen as an analog of Cheeger's inequality for the smallest eigenvalue of the adjacency matrix of a graph.) Iterating this procedure yields the approximation results stated above. A different, more complicated, variant of spectral partitioning leads to an O~(n3) time algorithm that cuts $1/2 + e^{-Omega(1/eps)}$ fraction of edges in graphs in which the optimum is 1/2+ϵ.