Minimum weight perfect matching via blossom belief propagation
- Title
- Minimum weight perfect matching via blossom belief propagation
- Authors
- AHN, SUNGSOO; Park, Sejun; Chertkov, Michael; Shin, Jinwoo
- Date Issued
- 2015-12
- Publisher
- Neural information processing systems foundation
- Abstract
- Max-product Belief Propagation (BP) is a popular message-passing algorithm for computing a Maximum-A-Posteriori (MAP) assignment over a distribution represented by a Graphical Model (GM). It has been shown that BP can solve a number of combinatorial optimization problems including minimum weight matching, shortest path, network flow and vertex cover under the following common assumption: the respective Linear Programming (LP) relaxation is tight, i.e., no integrality gap is present. However, when LP shows an integrality gap, no model has been known which can be solved systematically via sequential applications of BP. In this paper, we develop the first such algorithm, coined Blossom-BP, for solving the minimum weight matching problem over arbitrary graphs. Each step of the sequential algorithm requires applying BP over a modified graph constructed by contractions and expansions of blossoms, i.e., odd sets of vertices. Our scheme guarantees termination in O(n
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/109520
- Article Type
- Conference
- Citation
- 29th Annual Conference on Neural Information Processing Systems, NIPS 2015, page. 1288 - 1296, 2015-12
- Files in This Item:
- There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.