MAX CUT AND THE SMALLEST EIGENVALUE

We describe a new approximation algorithm for Max Cut. Our algorithm runs in (O) over tilde (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 - epsilon fraction of edges, our algorithm finds a solution that cuts a 1-4 root epsilon + 8 epsilon-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 - epsilon 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(root epsilon) fraction of the edges incident on S have one endpoint in L and one endpoint in R. (This can be seen as an analogue 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 a polynomial time algorithm that cuts a 1/2 + e(-Omega(1/epsilon)) fraction of edges in graphs in which the optimum is 1/2 + epsilon.