# Max-Product for Maximum Weight Matching - Revisited

arXiv: https://arxiv.org/abs/1805.06282 · HTML: https://mlsanity.com/paper/1805.06282/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 May 2018.

## Built on by (most cited first, 1 of 1)

- [New Auction Algorithms for Path Planning, Network Transport, and Reinforcement Learning](https://mlsanity.com/paper/2207.09588/) (2022)

## Abstract (arXiv)

We focus on belief propagation for the assignment problem, also known as the maximum weight bipartite matching problem. We provide a constructive proof that the well-known upper bound on the number of iterations (Bayati, Shah, Sharma 2008) is tight up to a factor of four. Furthermore, we investigate the behavior of belief propagation when convergence is not required. We show that the number of iterations required for a sharp approximation consumes a large portion of the convergence time. Finally, we propose an "approximate belief propagation" algorithm for the assignment problem.