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 2-338


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.