MIT Combinatorics Seminar
Applications of the Local Weak
Convergence Method to Random Graph Problems
David Gamarnik(IBM)
Friday, April 29, 2005 4:15 pm Room 2338
ABSTRACT

Local Weak Convergence method (LWC) exploits local structure (typically a
tree) of a large random combinatorial
object and leads to a complete asymptotic
solutions to several optimization problems
on random graphs. The method reduces the
original problem into the problem of
finding fixed points of a certain
distributional operator. We show that when
the fixed point of the second iterate of
the distributional operator is unique, it
determines the value of the underlying
combinatorial optimization problem.


