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

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

3 Citations (Scopus)

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öcking (SIAM J. Comput., 2006) for matching and generalize an isolation lemma for min-cost flow by Gamarnik, Shah, and Wei (Oper. Res., 2012). We also prove almost matching lower tail bounds for the number of iterations that BP needs to converge.
Original languageUndefined
Title of host publicationProceedings of the 7th International Workshop on Algorithms and Computation (WALCOM 2013)
EditorsS. Kumar Ghosh, T. Tokuyama
Place of PublicationBerlin, Germany
PublisherSpringer
Pages182-193
Number of pages12
ISBN (Print)978-3-642-36064-0
DOIs
Publication statusPublished - 2013

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
Volume7748

Keywords

  • EWI-22420
  • Message-passing algorithms
  • Smoothed Analysis
  • IR-83740
  • METIS-296431
  • Belief propagation
  • Min-cost flow
  • Combinatorial optimization
  • Matching

Cite this

Brunsch, T., Cornelissen, K., Manthey, B., & Röglin, H. (2013). Smoothed analysis of belief propagation for minimum-cost flow and matching. In S. Kumar Ghosh, & T. Tokuyama (Eds.), Proceedings of the 7th International Workshop on Algorithms and Computation (WALCOM 2013) (pp. 182-193). (Lecture Notes in Computer Science; Vol. 7748). Berlin, Germany: Springer. https://doi.org/10.1007/978-3-642-36065-7_18
Brunsch, Tobias ; Cornelissen, Kamiel ; Manthey, Bodo ; Röglin, Heiko. / Smoothed analysis of belief propagation for minimum-cost flow and matching. Proceedings of the 7th International Workshop on Algorithms and Computation (WALCOM 2013). editor / S. Kumar Ghosh ; T. Tokuyama. Berlin, Germany : Springer, 2013. pp. 182-193 (Lecture Notes in Computer Science).
@inproceedings{117c949588644af2afa2cf6b97c395ca,
title = "Smoothed analysis of belief propagation for minimum-cost flow and matching",
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 (Oper. Res., 2012). We also prove almost matching lower tail bounds for the number of iterations that BP needs to converge.",
keywords = "EWI-22420, Message-passing algorithms, Smoothed Analysis, IR-83740, METIS-296431, Belief propagation, Min-cost flow, Combinatorial optimization, Matching",
author = "Tobias Brunsch and Kamiel Cornelissen and Bodo Manthey and Heiko R{\"o}glin",
note = "10.1007/978-3-642-36065-7_18",
year = "2013",
doi = "10.1007/978-3-642-36065-7_18",
language = "Undefined",
isbn = "978-3-642-36064-0",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "182--193",
editor = "{Kumar Ghosh}, S. and T. Tokuyama",
booktitle = "Proceedings of the 7th International Workshop on Algorithms and Computation (WALCOM 2013)",

}

Brunsch, T, Cornelissen, K, Manthey, B & Röglin, H 2013, Smoothed analysis of belief propagation for minimum-cost flow and matching. in S Kumar Ghosh & T Tokuyama (eds), Proceedings of the 7th International Workshop on Algorithms and Computation (WALCOM 2013). Lecture Notes in Computer Science, vol. 7748, Springer, Berlin, Germany, pp. 182-193. https://doi.org/10.1007/978-3-642-36065-7_18

Smoothed analysis of belief propagation for minimum-cost flow and matching. / Brunsch, Tobias; Cornelissen, Kamiel; Manthey, Bodo; Röglin, Heiko.

Proceedings of the 7th International Workshop on Algorithms and Computation (WALCOM 2013). ed. / S. Kumar Ghosh; T. Tokuyama. Berlin, Germany : Springer, 2013. p. 182-193 (Lecture Notes in Computer Science; Vol. 7748).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

TY - GEN

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

AU - Brunsch, Tobias

AU - Cornelissen, Kamiel

AU - Manthey, Bodo

AU - Röglin, Heiko

N1 - 10.1007/978-3-642-36065-7_18

PY - 2013

Y1 - 2013

N2 - 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öcking (SIAM J. Comput., 2006) for matching and generalize an isolation lemma for min-cost flow by Gamarnik, Shah, and Wei (Oper. Res., 2012). We also prove almost matching lower tail bounds for the number of iterations that BP needs to converge.

AB - 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öcking (SIAM J. Comput., 2006) for matching and generalize an isolation lemma for min-cost flow by Gamarnik, Shah, and Wei (Oper. Res., 2012). We also prove almost matching lower tail bounds for the number of iterations that BP needs to converge.

KW - EWI-22420

KW - Message-passing algorithms

KW - Smoothed Analysis

KW - IR-83740

KW - METIS-296431

KW - Belief propagation

KW - Min-cost flow

KW - Combinatorial optimization

KW - Matching

U2 - 10.1007/978-3-642-36065-7_18

DO - 10.1007/978-3-642-36065-7_18

M3 - Conference contribution

SN - 978-3-642-36064-0

T3 - Lecture Notes in Computer Science

SP - 182

EP - 193

BT - Proceedings of the 7th International Workshop on Algorithms and Computation (WALCOM 2013)

A2 - Kumar Ghosh, S.

A2 - Tokuyama, T.

PB - Springer

CY - Berlin, Germany

ER -

Brunsch T, Cornelissen K, Manthey B, Röglin H. Smoothed analysis of belief propagation for minimum-cost flow and matching. In Kumar Ghosh S, Tokuyama T, editors, Proceedings of the 7th International Workshop on Algorithms and Computation (WALCOM 2013). Berlin, Germany: Springer. 2013. p. 182-193. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-642-36065-7_18