Belief propagation for minimum weight many-to-one matchings in the random complete graph
Abstract
In a complete bipartite graph with vertex sets of cardinalities $n$ and $n^\prime$, assign random weights from exponential distribution with mean 1, independently to each edge. We show that, as $n\rightarrow\infty$, with $n^\prime=\lceil n/\alpha\rceil$ for any fixed $\alpha>1$, the minimum weight of many-to-one matchings converges to a constant (depending on $\alpha$). Many-to-one matching arises as an optimization step in an algorithm for genome sequencing and as a measure of distance between finite sets. We prove that a belief propagation (BP) algorithm converges asymptotically to the optimal solution. We use the objective method of Aldous to prove our results. We build on previous works on minimum weight matching and minimum weight edge cover problems to extend the objective method and to further the applicability of belief propagation to random combinatorial optimization problems.
Full Text: Download PDF | View PDF online (requires PDF plugin)
Pages: 1-40
Publication Date: December 11, 2014
DOI: 10.1214/EJP.v19-3491
References
- Aldous, David. Asymptotics in the random assignment problem. Probab. Theory Related Fields 93 (1992), no. 4, 507–534. MR1183889
- Aldous, David; Lyons, Russell. Processes on unimodular random networks. Electron. J. Probab. 12 (2007), no. 54, 1454–1508. MR2354165
- Aldous, David; Steele, J. Michael. The objective method: probabilistic combinatorial optimization and local weak convergence. Probability on discrete structures, 1–72, Encyclopaedia Math. Sci., 110, Springer, Berlin, 2004. MR2023650
- Aldous, David J. The $\zeta(2)$ limit in the random assignment problem. Random Structures Algorithms 18 (2001), no. 4, 381–418. MR1839499
- Aldous, David J.; Bandyopadhyay, Antar. A survey of max-type recursive distributional equations. Ann. Appl. Probab. 15 (2005), no. 2, 1047–1110. MR2134098
- Bandyopadhyay, Antar. Endogeny for the logistic recursive distributional equation. Z. Anal. Anwend. 30 (2011), no. 2, 237–251. MR2793003
- Bayati, Mohsen; Shah, Devavrat; Sharma, Mayank. Max-product for maximum weight matching: convergence, correctness, and LP duality. IEEE Trans. Inform. Theory 54 (2008), no. 3, 1241–1251. MR2445062
- Ben-Dor, Amir; Karp, Richard M; Schwikowski, Benno; Shamir, Ron. The restriction scaffold problem. Journal of Computational Biology 10 (2003), no. 3-4, 385–398.
- Benjamini, Itai; Schramm, Oded. Recurrence of distributional limits of finite planar graphs. Electron. J. Probab. 6 (2001), no. 23, 13 pp. (electronic). MR1873300
- Blockeel, Hendrik; De Raedt, Luc; Ramong, Jan. Top-down induction of clustering trees. In Proceedings of the 15th International Conference on Machine Learning (1998), 55–63. Morgan Kaufmann.
- Eiter, Thomas; Mannila, Heikki. Distance measures for point sets and their computation. Acta Inform. 34 (1997), no. 2, 109–133. MR1465033
- Frieze, A. M. On the value of a random minimum spanning tree problem. Discrete Appl. Math. 10 (1985), no. 1, 47–56. MR0770868
- Frieze, Alan. On random symmetric travelling salesman problems. Math. Oper. Res. 29 (2004), no. 4, 878–890. MR2104159
- Hajek, Bruce. Performance of global load balancing by local adjustment. IEEE Trans. Inform. Theory 36 (1990), no. 6, 1398–1414. MR1080823
- Hessler, Martin; Wästlund, Johan. Edge cover and polymatroid flow problems. Electron. J. Probab. 15 (2010), no. 72, 2200–2219. MR2748403
- Khandwawala, Mustafa; Sundaresan, Rajesh. Belief propagation for optimal edge cover in the random complete graph. Ann. Appl. Probab. 24 (2014), no. 6, 2414–2454. MR3262507
- Mézard, Marc; Parisi, Giorgio. Replicas and optimization. Journal de Physique Lettres 46 (1985), 771–778.
- Mézard, Marc; Parisi, Giorgio. Mean-field equations for the matching and the travelling salesman problems. EPL (Europhysics Letters) 2 (1986), 913.
- Mézard, Marc; Parisi, Giorgio. On the solution of the random link matching problem. J.Physique 48 (1987), 1451–1459.
- Mézard, Marc; Parisi, Giorgio; Virasoro, Miguel Angel. Spin glass theory and beyond. World Scientific Lecture Notes in Physics, 9. World Scientific Publishing Co., Inc., Teaneck, NJ, 1987. xiv+461 pp. ISBN: 9971-50-115-5; 9971-50-116-3 MR1026102
- Parisi, Giorgio. A conjecture on random bipartite matching. arXiv:cond-mat/9801176 [cond-mat.dis-nn] (1998).
- Salez, Justin; Shah, Devavrat. Belief propagation: an asymptotically optimal algorithm for the random assignment problem. Math. Oper. Res. 34 (2009), no. 2, 468–480. MR2554069
- Sanghavi, Sujay; Malioutov, Dmitry; Willsky, Alan. Belief propagation and LP relaxation for weighted matching in general graphs. IEEE Trans. Inform. Theory 57 (2011), no. 4, 2203–2212. MR2760242
- Wästlund, Johan. The mean field traveling salesman and related problems. Acta Math. 204 (2010), no. 1, 91–150. MR2600434
- Wästlund, Johan. Replica symmetry of the minimum matching. Ann. of Math. (2) 175 (2012), no. 3, 1061–1091. MR2912702
This work is licensed under a Creative Commons Attribution 3.0 License.