{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T01:45:49Z","timestamp":1725500749732},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642360640"},{"type":"electronic","value":"9783642360657"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-36065-7_18","type":"book-chapter","created":{"date-parts":[[2013,1,21]],"date-time":"2013-01-21T16:36:53Z","timestamp":1358786213000},"page":"182-193","source":"Crossref","is-referenced-by-count":1,"title":["Smoothed Analysis of Belief Propagation for Minimum-Cost Flow and Matching"],"prefix":"10.1007","author":[{"given":"Tobias","family":"Brunsch","sequence":"first","affiliation":[]},{"given":"Kamiel","family":"Cornelissen","sequence":"additional","affiliation":[]},{"given":"Bodo","family":"Manthey","sequence":"additional","affiliation":[]},{"given":"Heiko","family":"R\u00f6glin","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"18_CR1","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network flows: theory, algorithms, and applications. Prentice-Hall (1993)"},{"issue":"2","key":"18_CR2","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-matching on arbitrary graphs and its relation to linear programs with integer solutions. SIAM Journal on Discrete Mathematics\u00a025(2), 989\u20131011 (2011)","journal-title":"SIAM Journal on Discrete Mathematics"},{"issue":"12","key":"18_CR3","doi-asserted-by":"publisher","first-page":"125206","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. Journal of Mathematical Physics\u00a049(12), 125206 (2008)","journal-title":"Journal of Mathematical Physics"},{"issue":"3","key":"18_CR4","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 Transactions on Information Theory\u00a054(3), 1241\u20131251 (2008)","journal-title":"IEEE Transactions on Information Theory"},{"issue":"4","key":"18_CR5","doi-asserted-by":"publisher","first-page":"855","DOI":"10.1137\/S0097539705447268","volume":"35","author":"R. Beier","year":"2006","unstructured":"Beier, R., V\u00f6cking, B.: Typical properties of winners and losers in discrete optimization. SIAM Journal in Computing\u00a035(4), 855\u2013881 (2006)","journal-title":"SIAM Journal in Computing"},{"issue":"2","key":"18_CR6","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 & correctness. Operations Research\u00a060(2), 410\u2013428 (2012)","journal-title":"Operations Research"},{"issue":"6","key":"18_CR7","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1524\/itit.2011.0654","volume":"53","author":"B. Manthey","year":"2011","unstructured":"Manthey, B., R\u00f6glin, H.: Smoothed analysis: Analysis of algorithms beyond worst case. IT \u2013 Information Technology\u00a053(6), 280\u2013286 (2011)","journal-title":"IT \u2013 Information Technology"},{"key":"18_CR8","doi-asserted-by":"crossref","unstructured":"Pearl, J.: Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann (1988)","DOI":"10.1016\/B978-0-08-051489-5.50008-4"},{"issue":"1","key":"18_CR9","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/s10107-006-0055-7","volume":"110","author":"H. R\u00f6glin","year":"2007","unstructured":"R\u00f6glin, H., V\u00f6cking, B.: Smoothed analysis of integer programming. Mathematical Programming\u00a0110(1), 21\u201356 (2007)","journal-title":"Mathematical Programming"},{"issue":"4","key":"18_CR10","doi-asserted-by":"publisher","first-page":"2203","DOI":"10.1109\/TIT.2011.2110170","volume":"57","author":"S. Sanghavi","year":"2011","unstructured":"Sanghavi, S., Malioutov, D.M., Willsky, A.S.: Belief propagation and LP relaxation for weighted matching in general graphs. IEEE Transactions on Information Theory\u00a057(4), 2203\u20132212 (2011)","journal-title":"IEEE Transactions on Information Theory"},{"issue":"11","key":"18_CR11","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 Transactions on Information Theory\u00a055(11), 4822\u20134834 (2009)","journal-title":"IEEE Transactions on Information Theory"},{"issue":"3","key":"18_CR12","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1145\/990308.990310","volume":"51","author":"D.A. Spielman","year":"2004","unstructured":"Spielman, D.A., Teng, S.-H.: Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. Journal of the ACM\u00a051(3), 385\u2013463 (2004)","journal-title":"Journal of the ACM"},{"issue":"10","key":"18_CR13","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1145\/1562764.1562785","volume":"52","author":"D.A. Spielman","year":"2009","unstructured":"Spielman, D.A., Teng, S.-H.: Smoothed analysis: An attempt to explain the behavior of algorithms in practice. Communications of the ACM\u00a052(10), 76\u201384 (2009)","journal-title":"Communications of the ACM"},{"key":"18_CR14","unstructured":"Yedidia, J.S., Freeman, W.T., Weiss, Y.: Understanding belief propagation and its generalizations. In: Lakemeyer, G., Nebel, B. (eds.) Exploring Artificial Intelligence in the New Millennium, ch. 8, pp. 239\u2013269. Morgan Kaufmann (2003)"}],"container-title":["Lecture Notes in Computer Science","WALCOM: Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-36065-7_18.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T13:34:55Z","timestamp":1620135295000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-36065-7_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642360640","9783642360657"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-36065-7_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}