TITLE:

THE PECULIAR PHASE STRUCTURE OF RANDOM GRAPH BISECTION

DATE:

Friday, April 8th, 2011

TIME:

3:30 PM

LOCATION:

GMCS 214

SPEAKER:

Allon G. Percus, Associate Professor, School of Mathematical Sciences at Claremont Graduate University

ABSTRACT:

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. 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.

This is joint work with Gabriel Istrate, Bruno Goncalves, Robert Sumi and Stefan Boettcher.

HOST:

Peter Salamon

DOWNLOAD:

PDF File