Iterative Message Passing Algorithm for Bipartite Maximum Weighted Matching
Yuansheng Cheng, Michael J. Neely, K.M. Chugg · 2006
We derive iterative message passing update rules for solving the bipartite maximum weighted matching problem. It is shown that if the optimal matching solution is unique, the algorithm converges to this optimal solution at a rate comparable to the algorithm of Bayati et. al. It is shown that the two algorithms are both standard messages passing, but on dual graphs of each other. Also, the algorithm presented here requires less storage. We also provide a method to use the proposed algorithm to solve the integer maximal weighted matching problem - i.e., where the optimal solution is generally not unique