TIME: 1:30-2:20 pm,  January 29, 2008

PLACE: CSE 503  

SPEAKER: Reid Andersen
         Microsoft Research

TITLE: An Algorithm for Improving Graph Partitions

ABSTRACT:
The minimum quotient cut problem is a fundamental and well-studied problem in
graph partitioning.  We present an algorithm called Improve that improves a
proposed partition of a graph, taking as input a subset of vertices and
returning a new subset of vertices with a smaller quotient cut score.  The most
powerful previously known method for improving quotient cuts, which is based on
parametric flow, returns a partition whose quotient cut score is at least as
small as any set contained within the proposed set.  For our algorithm, we can
prove a stronger guarantee: the quotient score of the set returned is nearly as
small as any set in the graph with which the proposed set has a
larger-than-expected intersection.  The algorithm finds such a set by solving a
sequence of polynomially many S-T minimum cut problems, a sequence that cannot
be cast as a single parametric flow problem.  We demonstrate empirically that
applying Improve to the output of various graph partitioning algorithms greatly
improves the quality of cuts produced without significantly impacting the
running time.