TY - GEN

T1 - Belief Propagation Min-Sum Algorithm for Generalized Min-Cost Network Flow

AU - Riazanov, Andrii

AU - Maximov, Yury

AU - Chertkov, Michael

PY - 2018/8/9

Y1 - 2018/8/9

N2 - Belief Propagation algorithms are instruments used broadly to solve graphical model optimization and statistical inference problems. In the general case of a loopy Graphical Model, Belief Propagation is a heuristic which is quite successful in practice, even though its empirical success, typically, lacks theoretical guarantees. This paper extends the short list of special cases where correctness and/or convergence of a Belief Propagation algorithm is proven. We generalize the formulation of Min-Sum Network Flow problem by relaxing the flow conservation (balance) constraints and then proving that the Belief Propagation algorithm converges to the exact result.

AB - Belief Propagation algorithms are instruments used broadly to solve graphical model optimization and statistical inference problems. In the general case of a loopy Graphical Model, Belief Propagation is a heuristic which is quite successful in practice, even though its empirical success, typically, lacks theoretical guarantees. This paper extends the short list of special cases where correctness and/or convergence of a Belief Propagation algorithm is proven. We generalize the formulation of Min-Sum Network Flow problem by relaxing the flow conservation (balance) constraints and then proving that the Belief Propagation algorithm converges to the exact result.

UR - http://www.scopus.com/inward/record.url?scp=85052582860&partnerID=8YFLogxK

U2 - 10.23919/ACC.2018.8431205

DO - 10.23919/ACC.2018.8431205

M3 - Conference contribution

AN - SCOPUS:85052582860

SN - 9781538654286

T3 - Proceedings of the American Control Conference

SP - 6108

EP - 6113

BT - 2018 Annual American Control Conference, ACC 2018

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2018 Annual American Control Conference, ACC 2018

Y2 - 27 June 2018 through 29 June 2018

ER -