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

Thursday, June 27, 2013

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.


Visiting Scholar
Coordinated Science Laboratory, University of Illinois at Urbana-Champaign
Rajesh Sundaresan is currently a visiting scholar at the Coordinated Science Laboratory, University of Illinois at Urbana-Champaign. He is an associate professor at the ECE department of the Indian Institute of Science, Bangalore. He is visiting the Coordinated Science Laboratory on an Indo-US Science and Technology Forum Fellowship. He received his Ph.D. in Electrical Engineering from Princeton University in 1999, designed wireless modems at Qualcomm Incorporated from 1999 to 2005, and joined the faculty of the Indian Institute of Science in 2005. His research interests are in the areas of information theory and networks.