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

This paper proves the correctness and convergence of max-product for finding the maximum weight matching (MWM) in bipartite graphs and provides a bound on the number of iterations required and it is shown that for a graph of size n, the computational cost of the algorithm scales as O(n3), which is the same as the computationalcost of the best known algorithms forFinding the MWM.

Abstract

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