Belief propagation : an asymptotically optimal algorithm for the random assignment problem

Understand

The random assignment problem asks for the minimum-cost perfect matching in the complete $n\times 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 $\zeta(2)$ as $n\to\infty$, as conjectured by M\'ezard 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) heuristic discussed by Pearl (1987).