ICS 2011

Welcome to ICS2011

Innovations in Computer Science - ICS 2011, Tsinghua University, Beijing, China, January 7-9, 2011. Proceedings, 367-388, 978-7-302-24517-9
Tsinghua University Press

Combinatorial Approximation Algorithms for MaxCut using Random Walks Authors : Satyen Kale, C. Seshadhri [Download PDF]

Abstract:
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 Õ(nb) algorithm that outputs a (0.5+δ)-approximation for MaxCut, where δ = δ(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 , unless a random walk of length Ɩ = O(log n) starting from i mixes rapidly (in terms of and Ɩ), we can find a cut of conductance at most close to the vertex. The work done per vertex found in the cut is sublinear in n.

Preview: