Belief Propagation and Algorithms for MeanField Combinatorial Optimisations
Abstract
We study combinatorial optimization problems on graphs in the meanfield model, which assigns independent and identically distributed random weights to the edges of the graph. Specifically, we focus on two generalizations of minimum weight matching on graphs. The ﬁrst problem of minimum cost edge cover finds application in a computational linguistics problem of semantic projection. The second problem of minimum cost manytoone matching appears as an intermediate optimization step in the restriction scaffold problem applied to shotgun sequencing of DNA.
For the minimum cost edge cover on a complete graph on n vertices, where the edge weights are independent exponentially distributed random variables, we show that the expectation of the minimum cost converges to a constant as n →∞ For the minimum cost manytoone matching on an n x m complete bipartite graph, scaling m as [ n/α ] for some fixed α > 1, we find the limit of the expected minimum cost as a function of α. For both problems, we show that a belief propagation algorithm converges asymptotically to the optimal solution. The belief propagation algorithm yields a near optimal solution with lesser complexity than the known best algorithms designed for optimality in worstcase settings.
Our proofs use the machinery of the objective method and local weak convergence, which are ideas developed by Aldous for proving the ζ(2) limit for the minimum cost bipartite matching. We use belief propagation as a constructive proof technique to supplement the objective method.
Recursive distributional equations(RDEs) arise naturally in the objective method approach. In a class of RDEs that arise as extensions of the minimum weight matching and travelling salesman problems, we prove existence and uniqueness of a fixed point distribution, and characterize its domain of attraction.
Collections
Related items
Showing items related by title, author, creator and subject.

Novel Mechanisms For Allocation Of Heterogeneous Items In Strategic Settings
Prakash, Gujar Sujit (20120420)Allocation of objects or resources to competing agents is a ubiquitous problem in the real world. For example, a federal government may wish to allocate different types of spectrum licenses to telecom service providers; a ... 
Hierarchical Logcut : A Fast And Efficient Way Of Energy Minimization Via Graph Cuts
Kulkarni, Gaurav (20130610)Graph cuts have emerged as an important combinatorial optimization tool for many problems in vision. Most of the computer vision problems are discrete labeling problems. For example, in stereopsis, labels represent disparity ... 
DegreeRegular Triangulations Of The Torus, The Klein Bottle And The DoubleTorus
Upadhyay, Ashish Kumar (20110928)