Belief Propagation for Min-Cost Network Flow: Convergence and Correctness
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 disciplin...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute for Operations Research and the Management Sciences (INFORMS)
2012
|
| Online Access: | http://hdl.handle.net/1721.1/72573 https://orcid.org/0000-0001-8898-8778 https://orcid.org/0000-0003-0737-3259 |
| _version_ | 1811079745764327424 |
|---|---|
| author | Gamarnik, David Shah, Devavrat Wei, Yehua |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Gamarnik, David Shah, Devavrat Wei, Yehua |
| author_sort | Gamarnik, David |
| collection | MIT |
| description | 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.
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—a 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. |
| first_indexed | 2024-09-23T11:19:53Z |
| format | Article |
| id | mit-1721.1/72573 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:19:53Z |
| publishDate | 2012 |
| publisher | Institute for Operations Research and the Management Sciences (INFORMS) |
| record_format | dspace |
| spelling | mit-1721.1/725732022-09-27T18:46:13Z Belief Propagation for Min-Cost Network Flow: Convergence and Correctness Gamarnik, David Shah, Devavrat Wei, Yehua Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Massachusetts Institute of Technology. Operations Research Center Sloan School of Management Shah, Devavrat Gamarnik, David Shah, Devavrat Wei, Yehua 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. 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—a 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. National Science Foundation (U.S.). Career Project (CNS 0546590) Natural Sciences and Engineering Research Council of Canada (NSERC). Postdoctoral Fellowship National Science Foundation (U.S.). EMT Project (CCF 0829893) National Science Foundation (U.S.). (CMMI-0726733) 2012-09-07T18:03:27Z 2012-09-07T18:03:27Z 2012-03 2010-08 Article http://purl.org/eprint/type/JournalArticle 0030-364X 1526-5463 http://hdl.handle.net/1721.1/72573 Gamarnik, D., D. Shah, and Y. Wei. “Belief Propagation for Min-Cost Network Flow: Convergence and Correctness.” Operations Research 60.2 (2012): 410–428. https://orcid.org/0000-0001-8898-8778 https://orcid.org/0000-0003-0737-3259 en_US http://dx.doi.org/10.1287/opre.1110.1025 Operations Research Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Institute for Operations Research and the Management Sciences (INFORMS) MIT web domain |
| spellingShingle | Gamarnik, David Shah, Devavrat Wei, Yehua Belief Propagation for Min-Cost Network Flow: Convergence and Correctness |
| title | Belief Propagation for Min-Cost Network Flow: Convergence and Correctness |
| title_full | Belief Propagation for Min-Cost Network Flow: Convergence and Correctness |
| title_fullStr | Belief Propagation for Min-Cost Network Flow: Convergence and Correctness |
| title_full_unstemmed | Belief Propagation for Min-Cost Network Flow: Convergence and Correctness |
| title_short | Belief Propagation for Min-Cost Network Flow: Convergence and Correctness |
| title_sort | belief propagation for min cost network flow convergence and correctness |
| url | http://hdl.handle.net/1721.1/72573 https://orcid.org/0000-0001-8898-8778 https://orcid.org/0000-0003-0737-3259 |
| work_keys_str_mv | AT gamarnikdavid beliefpropagationformincostnetworkflowconvergenceandcorrectness AT shahdevavrat beliefpropagationformincostnetworkflowconvergenceandcorrectness AT weiyehua beliefpropagationformincostnetworkflowconvergenceandcorrectness |