Home  Issues  Aims and Scope  Instructions for Authors 
DOI: 10.7155/jgaa.00310
Smoothed Analysis of Belief Propagation for MinimumCost Flow and Matching
Vol. 17, no. 6, pp. 647670, 2013. Regular paper.
Abstract Belief propagation (BP) is a messagepassing 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 remains limited. Recently, BP has been applied to combinatorial optimization problems. It has been proved that BP can be used to compute maximumweight matchings and minimumcost flows for instances with a unique optimum. The number of iterations needed for this is pseudopolynomial and hence BP is not efficient in general. We study BP in the framework of smoothed analysis and prove that with high probability the number of iterations needed to compute maximumweight matchings and minimumcost flows is bounded by a polynomial if the weights/costs of the edges are randomly perturbed. To prove our upper bounds, we use an isolation lemma by Beier and Vöcking (SIAM Journal on Computing, 2006) for the matching problem and we generalize an isolation lemma by Gamarnik, Shah, and Wei (Operations Research, 2012) for the mincost flow problem. We also prove lower tail bounds for the number of iterations that BP needs to converge that almost match our upper bounds.

Submitted: April 2013.
Reviewed: July 2013.
Revised: September 2013.
Reviewed: October 2013.
Revised: October 2013.
Accepted: October 2013.
Final: October 2013.
Published: November 2013.
Communicated by
Subir Kumar Ghosh
