Computer Science – Information Theory
Scientific paper
2005-08-23
IEEE Transactions on Information Theory, Vol 54 (3), 2008
Computer Science
Information Theory
In the proceedings of the 2005 IEEE International Symposium on Information Theory
Scientific paper
10.1109/TIT.2007.915695
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.
Bayati Mohsen
Shah Devavrat
Sharma Mayank
No associations
LandOfFree
Maximum Weight Matching via Max-Product Belief Propagation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Maximum Weight Matching via Max-Product Belief Propagation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Maximum Weight Matching via Max-Product Belief Propagation will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-165825