## 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.