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 (ℳ ℱ). 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 ℳ ℱ. This is the first instance where BP is proved to have fully-polynomial running time.