Copy of Belief propagation for some combinatorial optimization problems on the random complete graph

In this talk, I will highlight the main steps in applying Aldous's objective method to the problem of finding the minimum cost edge-cover of the complete graph with random independent and identically distributed edge-costs. Minimum cost edge-cover will be the example combinatorial optimization problem I will deal with, but the method applies to other similar problems such as matching. I will also discuss a belief propagation algorithm that converges to the optimal solution as the network size grows. The belief propagation algorithm is useful because it yields a near optimal solution with lesser complexity in the above random context, with lesser complexity than the best known algorithms designed for optimality in worst-case settings. The talk will be based on joint work with Mustafa Khandwawala.