KAIST Discrete Math Seminar

Belief propagation (BP) is a popular message-passing algorithm for computing a maximum-a-posteriori assignment in a graphical model. It has been shown that BP can solve a few classes of Linear Programming (LP) formulations to combinatorial optimization problems including maximum weight matching and shortest path. However, it has been not clear what extent these results can be generalized to. In this talk, I first present a generic criteria that BP converges to the optimal solution of given LP, and show that it is satisfied in LP formulations associated to many classical combinatorial optimization problems including maximum weight perfect matching, shortest path, network flow, traveling salesman, cycle packing and vertex cover. Using the criteria, we also construct the exact distributed algorithm, called Blossom-BP, solving the maximum weight matching problem over arbitrary graphs. In essence, Blossom-BP offers a distributed version of the celebrated Blossom algorithm (Edmonds 1965) jumping at once over many sub-steps of the Blossom-V (most recent implementation of the Blossom algorithm due to Kolmogorov, 2011). Finally, I report the empirical performance of BP for solving large-scale combinatorial optimization problems. This talk is based on a series of joint works with Sungsoo Ahn (KAIST), Michael Chertkov (LANL), Inho Cho (KAIST), Dongsu Han (KAIST) and Sejun Park (KAIST).