Belief propagation for min-cost network flow: Convergence & correctness

Journal Article

We formulate a Belief Propagation (BP) algorithm in the context of the capacitated minimum-cost network flow problem (MCF). Unlike most of the instances of BP studied in the past, the messages of BP in the context of this problem are piecewise-linear functions. We prove that BP converges to the optimal solution in pseudo-polynomial time, provided that the optimal solution is unique and the problem input is integral. Moreover, we present a simple modification of the BP algorithm which gives a fully polynomial-time randomized approximation scheme (FPRAS) for MCF. This is the first instance where BP is proved to have fully-polynomial running time. Copyright © by SIAM.

Full Text

Duke Authors

Cited Authors

  • Gamarnik, D; Shah, D; Wei, Y

Published Date

  • January 1, 2010

Published In

  • Proceedings of the Annual Acm Siam Symposium on Discrete Algorithms

Start / End Page

  • 279 - 292

Digital Object Identifier (DOI)

  • 10.1137/1.9781611973075.24

Citation Source

  • Scopus