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 opti...
Main Authors: | , , |
---|---|
Other Authors: | |
Format: | Article |
Language: | en_US |
Published: |
Society for Industrial and Applied Mathematics
2012
|
Online Access: | http://hdl.handle.net/1721.1/73521 https://orcid.org/0000-0001-8898-8778 https://orcid.org/0000-0003-0737-3259 |