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

Justin Salez, Devavrat Shah

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 r…