Max-Product for Maximum Weight Matching: Convergence, Correctness, and LP Duality

DOI10.1109/TIT.2007.915695zbMATH Open1311.90161arXivcs/0508101MaRDI QIDQ3604573FDOQ3604573

Devavrat Shah, Mohsen Bayati, M. Sharma

Publication date: 24 February 2009

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: Max-product "belief propagation" is an iterative, local, message-passing algorithm for finding the maximum a posteriori (MAP) assignment of a discrete probability distribution specified by a graphical model. Despite the spectacular success of the algorithm in many application areas such as iterative decoding, computer vision and combinatorial optimization which involve graphs with many cycles, theoretical results about both correctness and convergence of the algorithm are known in few cases (Weiss-Freeman Wainwright, Yeddidia-Weiss-Freeman, Richardson-Urbanke}. In this paper we consider the problem of finding the Maximum Weight Matching (MWM) in a weighted complete bipartite graph. We define a probability distribution on the bipartite graph whose MAP assignment corresponds to the MWM. We use the max-product algorithm for finding the MAP of this distribution or equivalently, the MWM on the bipartite graph. Even though the underlying bipartite graph has many short cycles, we find that surprisingly, the max-product algorithm always converges to the correct MAP assignment as long as the MAP assignment is unique. We provide a bound on the number of iterations required by the algorithm and evaluate the computational cost of the algorithm. We find that for a graph of size $n$, the computational cost of the algorithm scales as $O(n^3)$, which is the same as the computational cost of the best known algorithm. Finally, we establish the precise relation between the max-product algorithm and the celebrated {em auction} algorithm proposed by Bertsekas. This suggests possible connections between dual algorithm and max-product algorithm for discrete optimization problems.

Full work available at URL: https://arxiv.org/abs/cs/0508101

Recommendations

• The Maximum-Weight Stable Matching Problem: Duality and Efficiency
• Linear-time approximation for maximum weight matching
• New algorithms for maximum weight matching and a decomposition theorem
• Finding a complete matching with the maximum product on weighted bipartite graphs
• Efficient Algorithms for Weighted Rank-Maximal Matchings and Related Problems
• Maximum weight bipartite matching in matrix multiplication time
• scientific article; zbMATH DE number 7561396
• A simpler linear time \( \frac{2}{3} - \varepsilon\) approximation for maximum weight matching
• An Optimum Lower Bound for the Weights of Maximum Weight Matching in Bipartite Graphs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85)

Cited In (15)

• Convergence and correctness of belief propagation for weighted min-max flow
• The importance of memory for price discovery in decentralized markets
• Belief propagation for optimal edge cover in the random complete graph
• Convergence and correctness of belief propagation for the Chinese postman problem
• Fast Fitness Improvements in Estimation of Distribution Algorithms Using Belief Propagation
• Gauges, loops, and polynomials for partition functions of graphical models
• The patient-zero problem with noisy observations
• On Resolving Simultaneous Congruences Using Belief Propagation
• Belief propagation for the maximum-weight independent set and minimum spanning tree problems
• Optimizing social welfare for network bargaining games in the face of instability, greed and idealism
• On the optimality of solutions of the max-product belief-propagation algorithm in arbitrary graphs
• The random fractional matching problem
• Bargaining dynamics in exchange networks
• Random-link matching problems on random regular graphs
• Belief propagation for unbalanced assignment problem

This page was built for publication: Max-Product for Maximum Weight Matching: Convergence, Correctness, and LP Duality

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3604573)