When

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

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

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

Category

Applied Math Seminar

Speaker

Dr. Allon Percus (Los Alamos National Laboratory)

Abstract

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.

Where

CGU Math South, 710 N. College Ave.