Minimum Weight Perfect Matching via Blossom Belief Propagation
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 2 ) of BP runs, where n is the number of vertices in the original graph. In essence, the Blossom-BP offers a distributed version of the celebrated Edmonds' Blossom algorithm by jumping at once over many sub-steps with a single BP. Moreover, our result provides an interpretation of the Edmonds' algorithm as a sequence of LPs.
This paper introduces two polytime algorithms for minimumweight perfect matching using a sequence of linear programs orruns of max-product BP (the factor graphs for which areinspired by connections to the LPs). To obtain the polytimealgorithm using BP, the paper makes use of a result fromrecent prior work (Park and Shin, 2015): under specificconditions, for certain pairs of a factor graph and an LP,running max-product BP on the factor graph converges to thesolution of the LP. The paper proves that the iterativealgorithm uses at most O(n^2) iterations where n is the numberof vertices in the graph.The authors speculate that theirwork may spur further study of BP for MAP on more generalgraphical models. Though the paper does not explicitly stateany ideas in this direction, it seems like a furtile area. Aswell, the new LP algorithm provides an interesting contrastwith Edmonds' Blossom algorithm, which (in its original form)required exponentially many constraints. Overall, it's clearlywritten, original work that, while not the first polytimealgorithm for min-weight perfect matching (they reserve thattitle for (Chandrasekaren et al., 2012)), is likely thesimplest.  It seems the paper would benefit from a journal-stylepresentation: one which is more leisurely and examplefilled. Given space constraints the paper did a good job ofdelegating proofs of certain results to supplementarymaterial. However, the main paper would benefit greatly if theexamples from Appendix F could be included in a figure, andrepeatedly referenced through the description of thealgorithm.  On the one hand, this paper can be viewed as a niceapplication of Park and Shin (2015)'s BP/LP result. On theother, it stands as a unique example (to the best of myknowledge as well as claimed by the authors) of solving an ILPby repeated calls to BP.  This paper does not lack substance, but it would have beennice to see the algorithm put to use on some real matchingproblems. As the linear programming community knows well,polynomial time algorithms are sometimes less practical thantheir exponential time counterparts in the real world.  Misc:- line 155: Linear Programming --> Linear Program- line 190: this note deserves a one line explanation- line 196: initially confusing where T came from- line 258: if the proof of Theorem 3 will be left in theappendix, it would help to give some intuition for why thehalf-integral solution is obtained.- line 032 (appendix A): marginal beliefs --> max-marginals- A more detailed contrast with Chandrasekaren et al. (2012)seems appropriate