Show simple item record

dc.contributor.advisorSundareasan, Rajesh
dc.contributor.authorKhandwawala, Mustafa
dc.date.accessioned2017-11-15T07:23:01Z
dc.date.accessioned2018-07-31T04:49:00Z
dc.date.available2017-11-15T07:23:01Z
dc.date.available2018-07-31T04:49:00Z
dc.date.issued2017-11-15
dc.date.submitted2014
dc.identifier.urihttps://etd.iisc.ac.in/handle/2005/2764
dc.identifier.abstracthttp://etd.iisc.ac.in/static/etd/abstracts/3628/G26020-Abs.pdfen_US
dc.description.abstractWe 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.en_US
dc.language.isoen_USen_US
dc.relation.ispartofseriesG26020en_US
dc.subjectCombinatorial Optimizationen_US
dc.subjectBelief Propagation Algorithmsen_US
dc.subjectLocal Weak Convergenceen_US
dc.subjectRecursive Distributional Equations (RDEs)en_US
dc.subjectEdge-Coveren_US
dc.subjectMany-to-one Matchingsen_US
dc.subjectCombinatorial Probabilityen_US
dc.subjectMean Field Combinatorial Optimizationsen_US
dc.subjectMean-Field Modelen_US
dc.subjectCombinatorial Probabilityen_US
dc.subject.classificationComputer Scienceen_US
dc.titleBelief Propagation and Algorithms for Mean-Field Combinatorial Optimisationsen_US
dc.typeThesisen_US
dc.degree.namePhDen_US
dc.degree.levelDoctoralen_US
dc.degree.disciplineFaculty of Engineeringen_US


Files in this item

This item appears in the following Collection(s)

Show simple item record