A Simpler Max-Product Maximum Weight Matching Algorithm and the Auction Algorithm

The max-product “belief propagation” algorithm has received a lot of attention recently due to its spectacular success in many application areas such as iterative decoding, computer vision and combinatorial optimization. There is a lot of ongoing work investigating the theoretical properties of the algorithm. In our previous work (2005) we showed that the max-product algorithm can be used to solve the problem of finding the maximum weight matching (MWM) in a weighted complete bipartite graph. However, for a graph with n nodes the max-product algorithm requires O(n⁴) operations to find the MWM compared to O(n³) for best known algorithms such as those proposed by Edmonds and Karp (1972) and Bertsekas (1988). In this paper, we simplify the max-product algorithm to reduce the number of operations required to O(n³). The simplified algorithm has very similar dynamics to the well-known auction algorithm of Bertsekas (1988). To make this connection precise, we show that the max-product and auction algorithms, when slightly modified, are equivalent. We study the correctness of this modified algorithm. There is a tantalizing similarity between this connection and a recently observed connection between the max-product and LP-based algorithms for iterative decoding by Vontobel and Koetter.