A copy of this work was available on the public web and has been preserved in the Wayback Machine. The capture dates from 2013; you can also visit the original URL.
The file type is `application/pdf`

.

##
###
Belief Propagation: An Asymptotically Optimal Algorithm for the Random Assignment Problem

2009
*
Mathematics of Operations Research
*

The random assignment problem asks for the minimum-cost perfect matching in the complete n × n bipartite graph Knn with i.i.d. edge weights, say uniform on [0, 1]. In a remarkable work by Aldous (2001), the optimal cost was shown to converge to ζ(2) as n → ∞, as conjectured by Mézard and Parisi (1987) through the so-called cavity method. The latter also suggested a non-rigorous decentralized strategy for finding the optimum, which turned out to be an instance of the Belief Propagation (BP)

doi:10.1287/moor.1090.0380
fatcat:nlijecidzfa77a7seofpblxlua