TY - GEN
T1 - Belief Propagation Min-Sum Algorithm for Generalized Min-Cost Network Flow
AU - Riazanov, Andrii
AU - Maximov, Yury
AU - Chertkov, Michael
N1 - Funding Information:
*The work was supported by funding from the U.S. Department of Energy’s Office of Electricity as part of the DOE Grid Modernization Initiative.
Publisher Copyright:
© 2018 AACC.
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
UR - http://www.scopus.com/inward/citedby.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 -