2014/05/06 by Mustafa Khandwawala, Khandwawala, Mustafa
Computer Science · Biochemistry, Genetics and Molecular Biology · #Cooperative Communication and Network Coding #DNA and Biological Computing
paper · pdf · doi:10.48550/arxiv.1405.1292
In a complete bipartite graph with vertex sets of cardinalities n and m,\nassign random weights from exponential distribution with mean 1, independently\nto each edge. We show that, as n\→\∞, with m = lceil\nn/\α rceil for any fixed \α>1, the minimum weight of many-to-one\nmatchings converges to a constant (depending on \α). Many-to-one matching\narises as an optimization step in an algorithm for genome sequencing and as a\nmeasure of distance between finite sets. We prove that a belief propagation\n(BP) algorithm converges asymptotically to the optimal solution. We use the\nobjective method of Aldous to prove our results. We build on previous works on\nminimum weight matching and minimum weight edge-cover problems to extend the\nobjective method and to further the applicability of belief propagation to\nrandom combinatorial optimization problems.\n