DMMP Seminar

Kamiel Cornelissen — Smoothed Analysis of Belief Propagation for Minimum-Cost Flow and Matching

Time: Wednesday, December 19, 2012
Location: Room 311, Citadel

Belief propagation (BP) is a message-passing heuristic for statistical inference in graphical models such as Bayesian networks and Markov random fields. BP is used to compute marginal distributions or maximum likelihood assignments and has applications in many areas, including machine learning, image processing, and computer vision. However, the theoretical understanding of the performance of BP is unsatisfactory. Recently, BP has been applied to combinatorial optimization problems. It has been proved that BP can be used to compute maximum-weight matchings and min-cost ows for instances with a unique optimum. We introduce the BP heuristic and show how it can be used to compute maximum-weight matchings.