Smoothed analysis of belief propagation for minimum-cost flow and matching

DOI10.1007/978-3-642-36065-7_18MaRDI QIDQ4914447zbMATH OpenOpenAlexFDO

Authors Tobias Brunsch, Kamiel Cornelissen, Bodo Manthey, Heiko Röglin

Publication date 12 April 2013

Published in WALCOM: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1211.3299

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms (68W40) Combinatorial optimization (90C27)

Abstract: 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 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 belief propagation 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"{o}cking (SIAM J. Comput. 2006) for matching and generalize an isolation lemma for min-cost flow by Gamarnik, Shah, and Wei (Operations Research, 2012). We also prove almost matching lower tail bounds for the number of iterations that BP needs to converge.

Recommendations

• Smoothed analysis of belief propagation for minimum-cost flow and matching
• Belief propagation for min-cost network flow: convergence and correctness
• scientific article; zbMATH DE number 6297707
• Max-Product for Maximum Weight Matching: Convergence, Correctness, and LP Duality
• Belief Propagation for Weighted b-Matchings on Arbitrary Graphs and its Relation to Linear Programs with Integer Solutions

Cited in

(11)

• Belief propagation for the maximum-weight independent set and minimum spanning tree problems
• Convergence and correctness of belief propagation for the Chinese postman problem
• Smoothed analysis of belief propagation for minimum-cost flow and matching
• Belief propagation for min-cost network flow: convergence and correctness
• Belief propagation for continuous state spaces: stochastic message-passing with quantitative guarantees
• Belief propagation: an asymptotically optimal algorithm for the random assignment problem
• Derandomizing isolation in space-bounded settings
• scientific article; zbMATH DE number 6297707 (Why is no real title available?)
• Convergence of multivariate belief propagation, with applications to cuckoo hashing and load balancing
• Belief propagation for unbalanced assignment problem
• Convergence and correctness of belief propagation for weighted min-max flow

This page was built for publication: Smoothed analysis of belief propagation for minimum-cost flow and matching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4914447)