TITLE: Optimization and Statistical Physics: The interplay, and proofs of
the Parisi and Coppersmith-Sorkin conjectures
SPEAKER: Chandra Nair (Stanford University)
DATE: 2:00 - 3:00 P.M., Friday December 17, 2004
LOCATION: Tioga, 3U (PA)
ABSTRACT:
Optimization seeks to minimize a value function subject to constraints on the
solution set. It also seeks to obtain efficient algorithms for finding good
solutions. Statistical physics studies the evolution of systems governed by
local (microscopic) rules, and tries to quantify their global (macroscopic)
behavior. The Minimum Energy principle of physics states that these systems
evolve towards ground states. In a sense, physicists have been studying
optimization problems that occur in nature.
A particular branch of statistical physcics, called Spin Glass Theory, has
produced a number of remarkably effective methods for hard optimization problems
in Electrical Engineering and Computer Science.
This talk begins with a brief overview of the interplay between statistical
physics and optimization by considering various problems from Electrical
Engineering and Computer Science. I will then focus on the Random Assignment
Problem which arises in a variety of situations of practical interest; for
example, in finding minimum weight graph matchings, minimum cost paths/flows in
weighted graphs, etc.
By using the (non-rigorous) Replica Method of statistical physics, Mezard and
Parisi computed the average value of the minimum cost assignment to be pi^2/6 in
the "thermodynamic limit"; i.e. as the size of the system, N, goes to
infinity. Subsequently, Parisi conjectured that when the costs are independent,
rate 1, exponential random variables, the expected minimum cost for a system of
size N is 1/1^2 + 1/2^2 + ... + 1/N^2. This conjecture was later generalized by
Coppersmith and Sorkin.
I will present a proof of the Parisi and Coppersmith-Sorkin conjectures and
describe some consequences and connections. I will also show that the assignment
problem is equivalent to a minimum cost flow problem, and exploit this
connection to determine the asymptotic distribution of the minimum cost for a
special case of the assignment problem.
|
printable version
