Abstract
| Original language | Undefined |
|---|---|
| Title of host publication | Proceedings of the 7th International Workshop on Algorithms and Computation (WALCOM 2013) |
| Editors | S. Kumar Ghosh, T. Tokuyama |
| Place of Publication | Berlin, Germany |
| Publisher | Springer |
| Pages | 182-193 |
| Number of pages | 12 |
| ISBN (Print) | 978-3-642-36064-0 |
| DOIs | |
| Publication status | Published - 2013 |
Publication series
| Name | Lecture Notes in Computer Science |
|---|---|
| Publisher | Springer Verlag |
| Volume | 7748 |
Keywords
- EWI-22420
- Message-passing algorithms
- Smoothed Analysis
- IR-83740
- METIS-296431
- Belief propagation
- Min-cost flow
- Combinatorial optimization
- Matching
Cite this
}
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 proceeding › Conference contribution › Academic › peer-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 -