Belief Propagation for Min-cost Network Flow: Convergence and Correctness

Details Belief Propagation for Min-cost Network Flow: Convergence and Correctness Belief Propagation for Min-cost Network Flow: Convergence and Correctness

2010-04-09

arxiv.org/abs/1004.1586v3

Computer Science

Discrete Mathematics

This paper has been withdrawn as it is not up-to-date. The new version of this paper can be found at web.mit.edu/devavrat/ww

Scientific paper

Message passing type algorithms such as the so-called Belief Propagation algorithm have recently gained a lot of attention in the statistics, signal processing and machine learning communities as attractive algorithms for solving a variety of optimization and inference problems. As a decentralized, easy to implement and empirically successful algorithm, BP deserves attention from the theoretical standpoint, and here not much is known at the present stage. In order to fill this gap we consider the performance of the BP algorithm in the context of the capacitated minimum-cost network flow problem - the classical problem in the operations research field. We prove that BP converges to the optimal solution in the pseudo-polynomial time, provided that the optimal solution of the underlying problem 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 the same problem, which no longer requires the uniqueness of the optimal solution. This is the first instance where BP is proved to have fully-polynomial running time. Our results thus provide a theoretical justification for the viability of BP as an attractive method to solve an important class of optimization problems.

Affiliated with

Also associated with

No associations

Rating

Belief Propagation for Min-cost Network Flow: Convergence and Correctness does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Belief Propagation for Min-cost Network Flow: Convergence and Correctness, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Belief Propagation for Min-cost Network Flow: Convergence and Correctness will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-221479