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\).