ICS 2011

Welcome to ICS2011
Innovations in Computer Science  ICS 2011, Tsinghua University, Beijing, China, January 79, 2011. Proceedings, 367388, 9787302245179
Tsinghua University Press
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 factorrunning 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:

Copyright 20102011, Institute for Computer Science, Tsinghua University, All Rights Reserved.