Belief propagation for min-cost network flow: Convergence & correctness
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.
- Gamarnik, D; Shah, D; Wei, Y
- January 1, 2010
- Proceedings of the Annual Acm Siam Symposium on Discrete Algorithms
Start / End Page
- 279 - 292
Digital Object Identifier (DOI)