{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T02:18:16Z","timestamp":1787365096489,"version":"build-2736575974"},"reference-count":27,"publisher":"Institute of Electrical and Electronics Engineers (IEEE)","issue":"11","license":[{"start":{"date-parts":[[2009,11,1]],"date-time":"2009-11-01T00:00:00Z","timestamp":1257033600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/ieeexplore.ieee.org\/Xplorehelp\/downloads\/license-information\/IEEE.html"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEEE Trans. Inform. Theory"],"published-print":{"date-parts":[[2009,11]]},"DOI":"10.1109\/tit.2009.2030448","type":"journal-article","created":{"date-parts":[[2009,10,27]],"date-time":"2009-10-27T17:29:54Z","timestamp":1256664594000},"page":"4822-4834","source":"Crossref","is-referenced-by-count":85,"title":["Message Passing for Maximum Weight Independent Set"],"prefix":"10.1109","volume":"55","author":[{"given":"Sujay","family":"Sanghavi","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Devavrat","family":"Shah","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alan S.","family":"Willsky","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"263","reference":[{"key":"ref10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1561\/2200000001","article-title":"graphical models, exponential families, and variational inference","volume":"1","author":"wainwright","year":"2008","journal-title":"Found Trends Mach Learn"},{"key":"ref11","author":"yedidia","year":"2000","journal-title":"Generalized belief propagation"},{"key":"ref12","article-title":"map estimation, linear programming and belief propagation with convex free energies","author":"weiss","year":"2007","journal-title":"Proc 10th Conf Uncertainty in Artificial Intelligence"},{"key":"ref13","author":"bayati","year":"0","journal-title":"Belief-propagation for weighted b-matchings on arbitrary graphs and its relation to linear programs with integer solutions"},{"key":"ref14","first-page":"991","article-title":"on the relationship between linear programming decoding and min-sum algorithm decoding","author":"vontobel","year":"2004","journal-title":"Proc Int Symp Inf Theory Appl"},{"key":"ref15","first-page":"1281","author":"sanghavi","year":"2007","journal-title":"Advances in neural information processing systems"},{"key":"ref16","author":"schrijver","year":"2003","journal-title":"Combinatorial Optimization Polyhedra and Efficiency"},{"key":"ref17","author":"bertsekas","year":"1995","journal-title":"Non Linear Programming"},{"key":"ref18","first-page":"325","article-title":"polynomial algorithms for perfect graphs","volume":"21","author":"grotschel","year":"1984","journal-title":"Ann Discrete Math"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2007.4557418"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2006.200"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1007\/BF00247653"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1137\/0330025"},{"key":"ref6","author":"trevisan","year":"2004","journal-title":"Inapproximability of combinatorial optimization problems"},{"key":"ref5","author":"moallemi","year":"2006","journal-title":"Convergence of the min-sum message passing algorithm for quadratic optimization"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.856938"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1023\/B:STCO.0000021412.33763.d5"},{"key":"ref2","first-page":"1273","author":"sanghavi","year":"2007","journal-title":"Advances in neural information processing systems"},{"key":"ref9","author":"wainwright","year":"2003","journal-title":"Graphical models exponential families and variational inference"},{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2007.915695"},{"key":"ref20","article-title":"on optimality of tree-reweighted max-product message-passing","author":"kolmogorov","year":"2005","journal-title":"Proc 10th Conf Uncertainty in Artificial Intelligence"},{"key":"ref22","first-page":"553","author":"globerson","year":"2007","journal-title":"Advances in neural information processing systems"},{"key":"ref21","article-title":"map estimation, linear programming and belief propagation with convex free energies","author":"weiss","year":"2007","journal-title":"Proc 10th Conf Uncertainty in Artificial Intelligence"},{"key":"ref24","first-page":"276","article-title":"on the convergence of iterative decoding on graphs with a single cycle","author":"aji","year":"1998","journal-title":"Proc IEEE Int Symp Inf Theory"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1109\/18.910585"},{"key":"ref26","article-title":"loopy belief propagation and gibbs measures","author":"tatikonda","year":"2002","journal-title":"Proc 10th Conf Uncertainty in Artificial Intelligence"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.850085"}],"container-title":["IEEE Transactions on Information Theory"],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx5\/18\/5290270\/05290304.pdf?arnumber=5290304","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,10]],"date-time":"2021-10-10T23:52:23Z","timestamp":1633909943000},"score":1,"resource":{"primary":{"URL":"http:\/\/ieeexplore.ieee.org\/document\/5290304\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,11]]},"references-count":27,"journal-issue":{"issue":"11"},"URL":"https:\/\/doi.org\/10.1109\/tit.2009.2030448","relation":{},"ISSN":["0018-9448","1557-9654"],"issn-type":[{"value":"0018-9448","type":"print"},{"value":"1557-9654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,11]]}}}