ICS 2011

Welcome to ICS2011
Innovations in Computer Science  ICS 2011, Tsinghua University, Beijing, China, January 79, 2011. Proceedings, 321337, 9787302245179
Tsinghua University Press
We give a polynomial time algorithm that given a graph which admits a bisection cutting a fraction (1 − ε) of edges, finds a bisection cutting a (1 − g(ε)) fraction of edges where g(ε) → 0 as ε → 0. One can take g(ε) =O( log(1/ε)). Previously known algorithms for Max Bisection could only guarantee finding a bisection that cuts a fraction of edges bounded away from 1 (in fact less than 3/4) in such graphs. The known UniqueGames hardness results for Max Cut imply that one cannot achieve g(ε) ≤ C for some absolute constant C. Likewise, for the Min Bisection problem, if the graph has a bisection cutting at most εfraction of the edges, our methods enable finding a bisection cutting at most O( log(1/ε))fraction of the edges. The algorithms can also find cuts that are nearlybalanced (say with imbalance of at most 0.01) with value at least 1 − O( ) (for Max Bisection) and at most O( ) (for Min Bisection). These guarantees are optimal up to constant factors in the O( ) term under the Unique Games and related conjectures. Our general approach is simple to describe: First, we show how to solve the problems if the graph is an expander or if the graph consists of many disjoint components, each of small measure. Then, we show that every graph can be decomposed into disjoint components that are either expanders or have small measure, and how the cuts on different pieces may be merged appropriately. Preview:

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