Combinatorial Optimization, Phase Transitions, and the Peculiar Case of Graph Bisection

Start: 04/18/2008 - 2:00pm
End  : 04/18/2008 - 3:00pm

Applied Math Seminar

Dr. Allon Percus (Los Alamos National Laboratory)


Combinatorial optimization problems, where one must minimize an
objective function of possibly constrained discrete variables, are
fundamental to computation. One of the more surprising contributions to
combinatorial optimization over the past decade has come from
statistical physics. Numerous problems, such as graph coloring and
satisfiability, have been analyzed over random instances drawn from an
appropriately parametrized ensemble. (I will define all these
concepts.) What we have learned is that the behavior of optimization
algorithms over such ensembles correlates with an underlying phase
structure: the instances that are computationally hardest to solve are
concentrated near a phase transition. Insights into the connection
between these two phenomena have both transformed our understanding of
the performance of algorithms and inspired new algorithmic methods. I
will discuss results on the graph bisection problem that illustrate the
advantages -- as well as some limitations -- of this approach. For the
case of sparse random graphs, I will give an analytical upper bound on
the optimum cutsize that improves considerably upon previous bounds.
Combined with some recent observations on expander graphs, this bound
leads to two intriguing computational consequences: a) the phase
structure is quite unlike what other combinatorial optimization problems
display, and b) even though the problem is NP-hard, we can likely solve
typical instances near the phase transition in polynomial time.

CGU Math South, 710 N. College Ave.