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

Tobias Brunsch, Kamiel Cornelissen, Bodo Manthey +1

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 margi…