{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T22:24:01Z","timestamp":1778797441694,"version":"3.51.4"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2019,2,7]],"date-time":"2019-02-07T00:00:00Z","timestamp":1549497600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11871280"],"award-info":[{"award-number":["11871280"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11471003"],"award-info":[{"award-number":["11471003"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11471003"],"award-info":[{"award-number":["11471003"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004543","name":"China Scholarship Council","doi-asserted-by":"publisher","award":["201607910003"],"award-info":[{"award-number":["201607910003"]}],"id":[{"id":"10.13039\/501100004543","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Zhejiang Provincial Natural Science Foundation of China","award":["LY17A010017"],"award-info":[{"award-number":["LY17A010017"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11401389"],"award-info":[{"award-number":["11401389"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004543","name":"China Scholarship Council","doi-asserted-by":"publisher","award":["201608330111"],"award-info":[{"award-number":["201608330111"]}],"id":[{"id":"10.13039\/501100004543","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11871081"],"award-info":[{"award-number":["11871081"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11531014"],"award-info":[{"award-number":["11531014"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11871280"],"award-info":[{"award-number":["11871280"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11471003"],"award-info":[{"award-number":["11471003"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100013088","name":"Qing Lan Project","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100013088","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Glob Optim"],"published-print":{"date-parts":[[2019,11]]},"DOI":"10.1007\/s10898-019-00749-2","type":"journal-article","created":{"date-parts":[[2019,2,7]],"date-time":"2019-02-07T02:14:30Z","timestamp":1549505670000},"page":"813-831","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Convergence and correctness of belief propagation for the Chinese postman problem"],"prefix":"10.1007","volume":"75","author":[{"given":"Guowei","family":"Dai","sequence":"first","affiliation":[]},{"given":"Fengwei","family":"Li","sequence":"additional","affiliation":[]},{"given":"Yuefang","family":"Sun","sequence":"additional","affiliation":[]},{"given":"Dachuan","family":"Xu","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2224-1484","authenticated-orcid":false,"given":"Xiaoyan","family":"Zhang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,2,7]]},"reference":[{"key":"749_CR1","doi-asserted-by":"crossref","unstructured":"Achlioptas, D., Ricci-Tersenghi, F.: On the solution-space geometry of random constraint satisfaction problems. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pp. 130\u2013139, ACM (2006)","DOI":"10.1145\/1132516.1132537"},{"key":"749_CR2","unstructured":"Aji, S.M., Horn, G.B., Mceliece, R.J.: On the convergence of iterative decoding on graphs with a single cycle. In: Proceedings of IEEE International Symposium Information Theory, p. 276. Cambridge (1998)"},{"key":"749_CR3","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1109\/18.825794","volume":"46","author":"SM Aji","year":"2000","unstructured":"Aji, S.M., Mceliece, R.J.: The generalized distributive law. IEEE Trans. Inf. Theory 46, 325\u2013343 (2000)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"749_CR4","doi-asserted-by":"publisher","first-page":"857","DOI":"10.1063\/1.2982805","volume":"49","author":"M Bayati","year":"2008","unstructured":"Bayati, M., Braunstein, A., Zecchina, R.: A rigorous analysis of the cavity equations for the minimum spanning tree. J. Math. Phys. 49, 857\u2013883 (2008)","journal-title":"J. Math. Phys."},{"key":"749_CR5","doi-asserted-by":"publisher","first-page":"989","DOI":"10.1137\/090753115","volume":"25","author":"M Bayati","year":"2011","unstructured":"Bayati, M., Borgs, C., Chayes, J., Zecchina, R.: Belief propagation for weighted b-matchings on arbitrary graphs and its relation to linear programs with integer solutions. SIAM J. Discrete Math. 25, 989\u20131011 (2011)","journal-title":"SIAM J. Discrete Math."},{"key":"749_CR6","doi-asserted-by":"crossref","unstructured":"Bayati, M., Shah, D., Sharma, M.: A simpler max-product maximum weight matching algorithm and the auction algorithm. In: IEEE International Symposium Information Theory, pp. 557\u2013561 (2006)","DOI":"10.1109\/ISIT.2006.261778"},{"key":"749_CR7","doi-asserted-by":"publisher","first-page":"1241","DOI":"10.1109\/TIT.2007.915695","volume":"54","author":"M Bayati","year":"2008","unstructured":"Bayati, M., Shah, D., Sharma, M.: Max-product for maximum weight matching: convergence, correctness, and LP duality. IEEE Trans. Inf. Theory 54, 1241\u20131251 (2008)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"749_CR8","first-page":"182","volume-title":"Smoothed Analysis of Belief Propagation for Minimum-Cost Flow and Matching, WALCOM: algorithms and Computation","author":"T Brunsch","year":"2012","unstructured":"Brunsch, T., Cornelissen, K., Manthey, B., R\u00f6glin, H.: Smoothed Analysis of Belief Propagation for Minimum-Cost Flow and Matching, WALCOM: algorithms and Computation, pp. 182\u2013193. Springer, Berlin (2012)"},{"key":"749_CR9","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/s10898-007-9138-0","volume":"39","author":"DJ Chen","year":"2007","unstructured":"Chen, D.J., Lee, C.Y., Park, C.H., Mendes, P.: Parallelizing simulated annealing algorithms based on high-performance computer. J Glob. Optim. 39, 261\u2013289 (2007)","journal-title":"J Glob. Optim."},{"key":"749_CR10","unstructured":"Cheng, Y., Neely, M., Chugg, K.M.: Iterative message passing algorithm for bipartite maximum weighted matching. In: IEEE International Symposium Information Theory, Cambridge, pp. 1934\u20131938, (2006)"},{"key":"749_CR11","doi-asserted-by":"publisher","first-page":"881","DOI":"10.1017\/S096354830900981X","volume":"18","author":"A Coja-Oghlan","year":"2009","unstructured":"Coja-Oghlan, A., Mossel, E., Vilenchik, D.: A spectral approach to analysing belief propagation for 3-colouring. Comb. Probab. Comput. 18, 881\u2013912 (2009)","journal-title":"Comb. Probab. Comput."},{"key":"749_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/opre.13.1.1","volume":"13","author":"J Edmonds","year":"1965","unstructured":"Edmonds, J.: The Chinese postman problem. Oper. Res. 13, 1\u201373 (1965)","journal-title":"Oper. Res."},{"key":"749_CR13","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/BF01580113","volume":"5","author":"J Edmonds","year":"1973","unstructured":"Edmonds, J., Johnson, E.: Matching, Euler tour and Chinese postman. Math. Program. 5, 88\u2013124 (1973)","journal-title":"Math. Program."},{"key":"749_CR14","doi-asserted-by":"publisher","first-page":"5295","DOI":"10.1109\/TIT.2015.2466598","volume":"61","author":"G Even","year":"2015","unstructured":"Even, G., Halabi, N.: Analysis of the min-sum algorithm for packing and covering problems via linear programming. IEEE Trans. Inf. Theory 61, 5295\u20135305 (2015)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"749_CR15","first-page":"339","volume":"4110","author":"U Feige","year":"2010","unstructured":"Feige, U., Mossel, E., Vilenchik, D.: Complete convergence of message passing algorithms for some satisfiability problems. Random 4110, 339\u2013350 (2010)","journal-title":"Random"},{"key":"749_CR16","doi-asserted-by":"publisher","first-page":"972","DOI":"10.1126\/science.1136800","volume":"315","author":"BJ Frey","year":"2007","unstructured":"Frey, B.J., Dueck, D.: Clustering by passing messages between data points. Science 315, 972\u2013976 (2007)","journal-title":"Science"},{"key":"749_CR17","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1109\/TIT.2001.910571","volume":"47","author":"BJ Frey","year":"2001","unstructured":"Frey, B.J., Koetter, R., Forney Jr., G.D., Kschischang, F.R., Spielman, D.A.: Introduction to the special issue on codes on graphs and iterative algorithms. IEEE Trans. Inf. Theory 47, 493\u2013497 (2001)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"1","key":"749_CR18","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1109\/TIT.1962.1057683","volume":"8","author":"R. Gallager","year":"1962","unstructured":"Gallager, R.G.: Low density parity check codes. IEEE Trans. Inf. Theory 8, 21\u201328 (1962)","journal-title":"IEEE Transactions on Information Theory"},{"key":"749_CR19","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1287\/opre.1110.1025","volume":"60","author":"D Gamarnik","year":"2012","unstructured":"Gamarnik, D., Shah, D., Wei, Y.: Belief propagation for min-cost network flow: convergence and correctness. Oper. Res. 60, 410\u2013428 (2012)","journal-title":"Oper. Res."},{"key":"749_CR20","first-page":"273","volume":"1","author":"MG Guan","year":"1962","unstructured":"Guan, M.G.: Graphic programming using odd or even points. Chin. Math. 1, 273\u2013277 (1962)","journal-title":"Chin. Math."},{"key":"749_CR21","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1109\/18.910572","volume":"47","author":"FR Kschischang","year":"2001","unstructured":"Kschischang, F.R., Frey, B.J., Loeliger, H.-A.: Factor graphs and sum-product algorithm. IEEE Trans. Inf. Theory 47, 498\u2013519 (2001)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"749_CR22","doi-asserted-by":"publisher","first-page":"1685","DOI":"10.1126\/science.1086309","volume":"301","author":"M M\u00e9zard","year":"2003","unstructured":"M\u00e9zard, M.: Passing messages between disciplines. Science 301, 1685\u20131686 (2003)","journal-title":"Science"},{"key":"749_CR23","doi-asserted-by":"publisher","first-page":"812","DOI":"10.1126\/science.1073287","volume":"297","author":"M M\u00e9zard","year":"2002","unstructured":"M\u00e9zard, M., Parisi, G., Zecchina, R.: Analytic and algorithmic solution of random satisfiability problems. Science 297, 812\u2013815 (2002)","journal-title":"Science"},{"key":"749_CR24","first-page":"249","volume":"66","author":"M M\u00e9zard","year":"2002","unstructured":"M\u00e9zard, M., Zecchina, R.: Random k-satisfiability problem: from an analytic solution to an efficient algorithm. Phys. Rev. 66, 249\u2013264 (2002)","journal-title":"Phys. Rev."},{"key":"749_CR25","volume-title":"Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Reasoning","author":"J Pearl","year":"1988","unstructured":"Pearl, J.: Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Reasoning. Morgan Kaufman, San Mateo (1988)"},{"key":"749_CR26","doi-asserted-by":"publisher","first-page":"599","DOI":"10.1109\/18.910577","volume":"47","author":"T Richardson","year":"2001","unstructured":"Richardson, T., Urbanke, R.: The capacity of low-density parity check codes under message-passing decoding. IEEE Trans. Inf. Theory 47, 599\u2013618 (2001)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"749_CR27","unstructured":"Sanghavi, S., Malioutov, D., Willsky, A.: Linear programming analysis of loopy belief propagation for weighted matching. In: Advances in Neural Information Processing Systems, pp. 1273\u20131280. Cambridge, (2007)"},{"key":"749_CR28","doi-asserted-by":"publisher","first-page":"2203","DOI":"10.1109\/TIT.2011.2110170","volume":"54","author":"S Sanghavi","year":"2011","unstructured":"Sanghavi, S., Malioutov, D., Willsky, A.: Belief propagation and LP relaxation for weighted matching in general graphs. IEEE Trans. Inf. Theory 54, 2203\u20132212 (2011)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"749_CR29","doi-asserted-by":"publisher","first-page":"4822","DOI":"10.1109\/TIT.2009.2030448","volume":"55","author":"S Sanghavi","year":"2009","unstructured":"Sanghavi, S., Shah, D., Willsky, A.S.: Message passing for maximum weight independent set. IEEE Trans. Inf. Theory 55, 4822\u20134834 (2009)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"749_CR30","volume-title":"Combinatorial Optimization - Polyhedra and Efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization - Polyhedra and Efficiency. Springer, Berlin (2003)"},{"key":"749_CR31","unstructured":"Vontobel, P.O., Koetter, R.: Graph-cover decoding and finite-length analysis of message passing iterative decoding of LDPC codes, arXiv preprint cs\/0512078 (2005)"},{"key":"749_CR32","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1023\/B:STCO.0000021412.33763.d5","volume":"14","author":"M Wainwright","year":"2004","unstructured":"Wainwright, M., Jaakkola, T., Willsky, A.: Tree consistency and bounds on the performance of the max-product algorithm and its generalizations. Stat. Comput. 14, 143\u2013166 (2004)","journal-title":"Stat. Comput."},{"key":"749_CR33","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1162\/089976600300015880","volume":"12","author":"Y Weiss","year":"2000","unstructured":"Weiss, Y.: Correctness of local probability propagation in graphical models with loops. Neural Comput. 12, 1\u201342 (2000)","journal-title":"Neural Comput."},{"key":"749_CR34","doi-asserted-by":"publisher","first-page":"736","DOI":"10.1109\/18.910585","volume":"47","author":"Y Weiss","year":"2001","unstructured":"Weiss, Y., Freeman, W.: On the optimality of solutions of the max-product belief-propagation algorithm in arbitrary graphs. IEEE Trans. Inf. Theory 47, 736\u2013744 (2001)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"749_CR35","doi-asserted-by":"publisher","first-page":"2173","DOI":"10.1162\/089976601750541769","volume":"13","author":"Y Weiss","year":"2001","unstructured":"Weiss, Y., Freeman, W.: Correctness of belief propagation in Gaussian graphical models of arbitrary topology. Neural Comput. 13, 2173\u20132200 (2001)","journal-title":"Neural Comput."},{"key":"749_CR36","first-page":"236","volume":"8","author":"J Yedidia","year":"2003","unstructured":"Yedidia, J., Freeman, W., Weiss, Y.: Understanding belief propagation and its generalizations. Explor. Artif. Intell. New Millenn. 8, 236\u2013239 (2003)","journal-title":"Explor. Artif. Intell. New Millenn."}],"container-title":["Journal of Global Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10898-019-00749-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-019-00749-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-019-00749-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,2,6]],"date-time":"2020-02-06T19:17:31Z","timestamp":1581016651000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10898-019-00749-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,2,7]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,11]]}},"alternative-id":["749"],"URL":"https:\/\/doi.org\/10.1007\/s10898-019-00749-2","relation":{},"ISSN":["0925-5001","1573-2916"],"issn-type":[{"value":"0925-5001","type":"print"},{"value":"1573-2916","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,2,7]]},"assertion":[{"value":"27 June 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 January 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 February 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}