Belief propagation for optimal edge cover in the random complete graph. (English) Zbl 1318.60016

This article studies the minimum cost edge cover problem on the complete graph, where the edge costs are random independent and identically distributed. The article begins with a review of the literature on the problem, followed by a presentation of the main result which is the limit of the optimal cost as the number of vertices goes to infinity. Moreover, it is established that a belief propagation algorithm, presented in the article, provides an edge cover which is asymptotically optimal as the number of vertices goes to infinity. The authors provide a very large number of useful results via proven theorems. A list of useful references concludes this interesting article.


60C05 Combinatorial probability
68Q87 Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
82B44 Disordered systems (random Ising models, random Schrödinger operators, etc.) in equilibrium statistical mechanics
05C80 Random graphs (graph-theoretic aspects)
Full Text: DOI arXiv Euclid


[1] Aldous, D. (1992). Asymptotics in the random assignment problem. Probab. Theory Related Fields 93 507-534. · Zbl 0767.60006 · doi:10.1007/BF01192719
[2] Aldous, D. and Lyons, R. (2007). Processes on unimodular random networks. Electron. J. Probab. 12 1454-1508. · Zbl 1131.60003 · doi:10.1214/EJP.v12-463
[3] Aldous, D. and Steele, J. M. (2004). The objective method: Probabilistic combinatorial optimization and local weak convergence. In Probability on Discrete Structures. Encyclopaedia Math. Sci. 110 1-72. Springer, Berlin. · Zbl 1037.60008 · doi:10.1007/978-3-662-09444-0_1
[4] Aldous, D. J. (2001). The \(\zeta(2)\) limit in the random assignment problem. Random Structures Algorithms 18 381-418. · Zbl 0993.60018 · doi:10.1002/rsa.1015
[5] Aldous, D. J. and Bandyopadhyay, A. (2005). A survey of max-type recursive distributional equations. Ann. Appl. Probab. 15 1047-1110. · Zbl 1105.60012 · doi:10.1214/105051605000000142
[6] Bandyopadhyay, A. (2011). Endogeny for the logistic recursive distributional equation. Z. Anal. Anwend. 30 237-251. · Zbl 1215.60009 · doi:10.4171/ZAA/1433
[7] Bayati, M., Shah, D. and Sharma, M. (2008). Max-product for maximum weight matching: Convergence, correctness, and LP duality. IEEE Trans. Inform. Theory 54 1241-1251. · Zbl 1311.90161 · doi:10.1109/TIT.2007.915695
[8] Frieze, A. M. (1985). On the value of a random minimum spanning tree problem. Discrete Appl. Math. 10 47-56. · Zbl 0578.05015 · doi:10.1016/0166-218X(85)90058-7
[9] Hajek, B. (1990). Performance of global load balancing by local adjustment. IEEE Trans. Inform. Theory 36 1398-1414. · Zbl 0716.90065 · doi:10.1109/18.59935
[10] Hessler, M. and Wästlund, J. (2010). Edge cover and polymatroid flow problems. Electron. J. Probab. 15 2200-2219. · Zbl 1226.90124
[11] Mézard, M. and Parisi, G. (1987). On the solution of the random link matching problem. J. Physique 48 1451-1459.
[12] Padó, S. and Lapata, M. (2006). Optimal constituent alignment with edge covers for semantic projection. In Proceedings of the 21 st International Conference on Computational Linguistics and the 44 th Annual Meeting of the Association for Computational Linguistics 1161-1168. Association for Computational Linguistics, Stroudsburg, PA.
[13] Padó, S. and Lapata, M. (2009). Cross-lingual annotation projection for semantic roles. J. Artificial Intelligence Res. 36 307-340. · Zbl 1192.68713 · doi:10.1613/jair.2863
[14] Salez, J. and Shah, D. (2009). Belief propagation: An asymptotically optimal algorithm for the random assignment problem. Math. Oper. Res. 34 468-480. · Zbl 1230.68183 · doi:10.1287/moor.1090.0380
[15] Schrijver, A. (2003). Combinatorial Optimization. Polyhedra and Efficiency. Vol. A. Algorithms and Combinatorics 24 . Paths , Flows , Matchings . Springer, Berlin. · Zbl 1041.90001
[16] Wästlund, J. (2009). Replica symmetry and combinatorial optimization. Available at [math.PR]. 0908.1920
[17] Wästlund, J. (2010). The mean field traveling salesman and related problems. Acta Math. 204 91-150. · Zbl 1231.90370 · doi:10.1007/s11511-010-0046-7
[18] Wästlund, J. (2012). Replica symmetry of the minimum matching. Ann. of Math. (2) 175 1061-1091. · Zbl 1262.91046 · doi:10.4007/annals.2012.175.3.2
[19] Wikipedia (2012). Semantic role labeling. 22 March 2012. Available at .
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.