Summary: The random assignment problem asks for the minimum-cost perfect matching in the complete \(n\times n\) bipartite graph \(\mathcal{K}_{nn}\) with i.i.d. edge weights, say uniform on \([0, 1]\). In a remarkable work by D. J. Aldous [Random Struct. Algorithms 18, No. 4, 381–418 (2001; Zbl 0993.60018)], the optimal cost was shown to converge to \(\zeta(2)\) as \(n\to\infty\), as conjectured by M. Mézard and G. Parisi [“On the solution of the random link matching problem”, J. Phys. 48, 1451–1459 (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 J. Pearl [Probabilistic reasoning in intelligent systems: networks of plausible inference. San Mateo etc.: Morgan Kaufmann Publishers (1989; Zbl 0746.68089)].
In this paper we use the objective method to analyze the performance of BP as the size of the underlying graph becomes large. Specifically, we establish that the dynamic of BP on \(\mathcal{K}_{nn}\) converges in distribution as \(n\to\infty\) to an appropriately defined dynamic on the Poisson weighted infinite tree, and we then prove a correlation decay for this limiting dynamic. As a consequence, we obtain that BP finds an asymptotically correct assignment in \(O(n^2)\) time only. This contrasts with both the worst-case upper bound for convergence of BP derived by M. Bayati, D. Shah and M. Sharma [“Max-product for maximum weight matching: convergence, correctness, and LP duality”, IEEE Trans. Inform. Theory 54, No. 3, 1241–1251 (2008)] and the best-known computational cost of \(\Theta(n^3)\) achieved by the algorithm of J. Edmonds and R. M. Karp [J. Assoc. Comput. Mach. 19, 248–264 (1972; Zbl 0318.90024)].