Geodesic
Smoothed Analysis of Belief Propagation for Minimum-Cost Flow and Matching
Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the Seventh International Workshop on Algorithms and Computation, WALCOM 2013 , Tome 17 (2013) no. 6, pp. 647-670.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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 remains limited. Recently, BP has been applied to combinatorial optimization problems. It has been proved that BP can be used to compute maximum-weight matchings and minimum-cost flows for instances with a unique optimum. The number of iterations needed for this is pseudo-polynomial 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 maximum-weight matchings and minimum-cost 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 min-cost flow problem. We also prove lower tail bounds for the number of iterations that BP needs to converge that almost match our upper bounds.
DOI : 10.7155/jgaa.00310
Keywords: belief propagation, smoothed analysis, matching, minimum-cost flow 
@article{JGAA_2013_17_6_a4,
     author = {Tobias Brunsch and Kamiel Cornelissen and Bodo Manthey and Heiko R\"oglin},
     title = {Smoothed {Analysis} of {Belief} {Propagation} for {Minimum-Cost} {Flow} and {Matching}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {647--670},
     publisher = {mathdoc},
     volume = {17},
     number = {6},
     year = {2013},
     doi = {10.7155/jgaa.00310},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00310/}
}
TY  - JOUR
AU  - Tobias Brunsch
AU  - Kamiel Cornelissen
AU  - Bodo Manthey
AU  - Heiko Röglin
TI  - Smoothed Analysis of Belief Propagation for Minimum-Cost Flow and Matching
JO  - Journal of Graph Algorithms and Applications
PY  - 2013
SP  - 647
EP  - 670
VL  - 17
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00310/
DO  - 10.7155/jgaa.00310
LA  - en
ID  - JGAA_2013_17_6_a4
ER  - 
%0 Journal Article
%A Tobias Brunsch
%A Kamiel Cornelissen
%A Bodo Manthey
%A Heiko Röglin
%T Smoothed Analysis of Belief Propagation for Minimum-Cost Flow and Matching
%J Journal of Graph Algorithms and Applications
%D 2013
%P 647-670
%V 17
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00310/
%R 10.7155/jgaa.00310
%G en
%F JGAA_2013_17_6_a4
Tobias Brunsch; Kamiel Cornelissen; Bodo Manthey; Heiko Röglin. Smoothed Analysis of Belief Propagation for Minimum-Cost Flow and Matching. Journal of Graph Algorithms and Applications, 
							Special Issue on Selected Papers from the Seventh International Workshop on Algorithms and Computation, WALCOM 2013
					, Tome 17 (2013) no. 6, pp. 647-670. doi : 10.7155/jgaa.00310. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00310/

Cité par Sources :