Satyen Kale and C. Seshadhri
Proceedings of 2nd Symposium on Innovations in Computer Science (ICS), 2011

We give the first combinatorial approximation algorithm for Maxcut that beats the trivial 0.5 factor by a constant. The main partitioning procedure is very intuitive, natural, and easily described. It essentially performs a number of random walks and aggregates the information to provide the partition. We can control the running time to get an approximation factor-running time tradeoff. We show that for any constant \(b > 1.5\), there is an \(O(n^b)\) algorithm that outputs a \((0.5+\delta)\) approximation for Maxcut, where \(\delta = \delta(b)\) is some positive constant.

One of the components of our algorithm is a weak local graph partitioning procedure that may be of independent interest. Given a starting vertex \(i\) and a conductance parameter \(\phi\), unless a random walk of length \(l = O(\log n)\) starting from \(i\) mixes rapidly (in terms of \(\phi\) and \(l\)), we can find a cut of conductance at most \(\phi\) close to the vertex. The work done per vertex found in the cut is sublinear in \(n\).