Title: Combinatorial Approximation Algorithms for MaxCut
using Random Walks
Speaker: C. Seshadhri (Sandia National Labs, Livermore)
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 O(n^b)-time combinatorial algorithm that outputs a
(0.5+delta)-approximation for Maxcut, where delta = delta(b) is some positive
constant. The analysis of this algorithm goes via Trevisan's eigenvalue
analysis for MaxCut. One of the components of our algorithm is a weak local
graph partitioning procedure that may be of independent interest.
Joint work with Satyen Kale. To appear in ICS 2011.