Record Details

Belief Propagation and Algorithms for Mean-Field Combinatorial Optimisations

Electronic Theses of Indian Institute of Science

View Archive Info
 
 
Field Value
 
Title Belief Propagation and Algorithms for Mean-Field Combinatorial Optimisations
 
Creator Khandwawala, Mustafa
 
Subject Combinatorial Optimization
Belief Propagation Algorithms
Local Weak Convergence
Recursive Distributional Equations (RDEs)
Edge-Cover
Many-to-one Matchings
Combinatorial Probability
Mean Field Combinatorial Optimizations
Mean-Field Model
Combinatorial Probability
Computer Science
 
Description We study combinatorial optimization problems on graphs in the mean-field 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 first problem of minimum cost edge cover finds application in a computational linguistics problem of semantic projection. The second problem of minimum cost many-to-one 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 many-to-one 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 worst-case 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.
 
Contributor Sundareasan, Rajesh
 
Date 2017-11-15T07:23:01Z
2017-11-15T07:23:01Z
2017-11-15
2014
 
Type Thesis
 
Identifier http://hdl.handle.net/2005/2764
http://etd.ncsi.iisc.ernet.in/abstracts/3628/G26020-Abs.pdf
 
Language en_US
 
Relation G26020