Optimality of belief propagation for random assignment problem
Justin Salez, Devavrat Shah · 2009
The assignment problem concerns finding the minimum-cost perfect matching in a complete weighted n × n bipartite graph. Any algorithm for this classical question clearly requires Ω(n 2) time, and the best known one (Edmonds and Karp, 1972) finds solution in O(n³). For decades, it has remained unknown whether optimal computation time is closer to n 3 or n 2. We provide answer to this question for random instance of assignment problem. Specifically, we establish that Belief Propagation finds solution in O(n²) time when edge-weights are i.i.d. with light tailed distribution.