{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,1]],"date-time":"2025-05-01T05:27:55Z","timestamp":1746077275972},"reference-count":31,"publisher":"Institute for Operations Research and the Management Sciences (INFORMS)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Operations Research"],"published-print":{"date-parts":[[2012,4]]},"abstract":" Distributed, iterative algorithms operating with minimal data structure while performing little computation per iteration are popularly known as message passing in the recent literature. Belief propagation (BP), a prototypical message-passing algorithm, has gained a lot of attention across disciplines, including communications, statistics, signal processing, and machine learning as an attractive, scalable, general-purpose heuristic for a wide class of optimization and statistical inference problems. Despite its empirical success, the theoretical understanding of BP is far from complete. <\/jats:p> With the goal of advancing the state of art of our understanding of BP, we study the performance of BP in the context of the capacitated minimum-cost network flow problem\u2014a cornerstone in the development of the theory of polynomial-time algorithms for optimization problems and widely used in the practice of operations research. As the main result of this paper, we prove that BP converges to the optimal solution in pseudopolynomial time, provided that the optimal solution of the underlying network flow problem instance is unique and the problem parameters are integral. We further provide a simple modification of the BP to obtain a fully polynomial-time randomized approximation scheme (FPRAS) without requiring 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. <\/jats:p>","DOI":"10.1287\/opre.1110.1025","type":"journal-article","created":{"date-parts":[[2012,5,16]],"date-time":"2012-05-16T17:38:33Z","timestamp":1337189913000},"page":"410-428","source":"Crossref","is-referenced-by-count":33,"title":["Belief Propagation for Min-Cost Network Flow: Convergence and Correctness"],"prefix":"10.1287","volume":"60","author":[{"given":"David","family":"Gamarnik","sequence":"first","affiliation":[{"name":"Operations Research Center and Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139"}]},{"given":"Devavrat","family":"Shah","sequence":"additional","affiliation":[{"name":"Laboratory for Information and Decision Systems (LIDS) and Operations Research Center, Department of EECS, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139"}]},{"given":"Yehua","family":"Wei","sequence":"additional","affiliation":[{"name":"Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139"}]}],"member":"109","reference":[{"key":"B1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585705"},{"key":"B2","volume-title":"Network Flows","author":"Ahuja R. K.","year":"1993"},{"key":"B3","doi-asserted-by":"publisher","DOI":"10.1109\/18.825794"},{"key":"B4","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2007.915695"},{"key":"B5","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2008\/06\/L06001"},{"key":"B6","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.1986.267433"},{"key":"B7","unstructured":"Bertsimas D., Tsitsiklis J.Introduction to Linear Optimization (1997) 3rd ed.(Athena Scientific, Belmont, MA) 289\u2013290"},{"key":"B8","doi-asserted-by":"publisher","DOI":"10.1145\/321694.321699"},{"key":"B9","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580882"},{"key":"B10","doi-asserted-by":"crossref","unstructured":"Gallager R. Low density parity check codes. (1963) . Ph.D. thesis, Massachusetts Institute of Technology, Cambridge, MA","DOI":"10.7551\/mitpress\/4347.001.0001"},{"key":"B11","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973075.24"},{"key":"B12","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28397"},{"key":"B13","doi-asserted-by":"publisher","DOI":"10.1145\/76359.76368"},{"key":"B14","unstructured":"Horn G. B. Iterative decoding and pseudocodewords. (1999) . Ph.D. thesis, California Institute of Technology, Pasadena, CA"},{"key":"B15","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.118"},{"key":"B16","first-page":"2031","volume":"7","author":"Malioutov D. M.","year":"2006","journal-title":"J. Machine Learning Res."},{"key":"B17","doi-asserted-by":"publisher","DOI":"10.1126\/science.1073287"},{"key":"B18","volume-title":"45th Allerton Conf. Comm., Control, Comput.","author":"Moallemi C. C.","year":"2007"},{"key":"B19","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2009.2016055"},{"key":"B20","volume-title":"45th Allerton Conf. Comm., Control, Comput.","author":"Montanari A.","year":"2007"},{"key":"B21","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579206"},{"key":"B22","doi-asserted-by":"publisher","DOI":"10.1287\/opre.41.2.338"},{"key":"B23","volume-title":"Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference","author":"Pearl J.","year":"1988"},{"key":"B24","doi-asserted-by":"publisher","DOI":"10.1109\/18.910577"},{"key":"B25","first-page":"181","author":"R\u00f6ck H.","year":"1980","journal-title":"Discrete Structures Algorithms"},{"key":"B26","doi-asserted-by":"publisher","DOI":"10.1109\/ALLERTON.2008.4797655"},{"key":"B27","volume-title":"Proc. NIPS Conf.","author":"Sanghavi S.","year":"2007"},{"key":"B28","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2009.2030448"},{"key":"B29","volume-title":"Combinatorial Optimization","author":"Schrijver A.","year":"2003"},{"key":"B30","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579369"},{"key":"B31","doi-asserted-by":"publisher","DOI":"10.1109\/18.910585"}],"container-title":["Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/pubsonline.informs.org\/doi\/pdf\/10.1287\/opre.1110.1025","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,2]],"date-time":"2023-04-02T15:03:57Z","timestamp":1680447837000},"score":1,"resource":{"primary":{"URL":"https:\/\/pubsonline.informs.org\/doi\/10.1287\/opre.1110.1025"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,4]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2012,4]]}},"alternative-id":["10.1287\/opre.1110.1025"],"URL":"https:\/\/doi.org\/10.1287\/opre.1110.1025","relation":{},"ISSN":["0030-364X","1526-5463"],"issn-type":[{"value":"0030-364X","type":"print"},{"value":"1526-5463","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,4]]}}}