{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:30:09Z","timestamp":1750221009174,"version":"3.41.0"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2019,8,17]],"date-time":"2019-08-17T00:00:00Z","timestamp":1566000000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CNS-1010789, CCF-1422569, CCF-1749864"],"award-info":[{"award-number":["CNS-1010789, CCF-1422569, CCF-1749864"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Amazon, Inc."},{"name":"Adobe, Inc"},{"name":"Google, Inc"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2019,10,31]]},"abstract":"<jats:p>\n            The resampling algorithm of Moser and Tardos is a powerful approach to develop constructive versions of the Lov\u00e1sz Local Lemma. We generalize this to\n            <jats:italic>partial<\/jats:italic>\n            resampling: When a bad event holds, we resample an appropriately random\n            <jats:italic>subset<\/jats:italic>\n            of the variables that define this event rather than the entire set, as in Moser and Tardos. This is particularly useful when the bad events are determined by sums of random variables. This leads to several improved algorithmic applications in scheduling, graph transversals, packet routing, and so on. For instance, we settle a conjecture of Szab\u00f3 and Tardos (2006) on graph transversals asymptotically and obtain improved approximation ratios for a packet routing problem of Leighton, Maggs, and Rao (1994).\n          <\/jats:p>","DOI":"10.1145\/3342222","type":"journal-article","created":{"date-parts":[[2019,8,19]],"date-time":"2019-08-19T19:41:32Z","timestamp":1566243692000},"page":"1-45","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["The Moser--Tardos Framework with Partial Resampling"],"prefix":"10.1145","volume":"66","author":[{"given":"David G.","family":"Harris","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Maryland, College Park, MD 20742"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aravind","family":"Srinivasan","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Institute for Advanced Computer Studies, University of Maryland, College Park, MD 20742"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,8,17]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-007-2086-y"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02783300"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240030102"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060639"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548311000253"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(75)90011-4"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201916). 1984","author":"Chen A.","year":"2003","unstructured":"A. Chen , D. Harris , and A. Srinivasan . 2016. Partial resampling to approximate covering integer programs . In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201916). 1984 -- 2003 . A. Chen, D. Harris, and A. Srinivasan. 2016. Partial resampling to approximate covering integer programs. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201916). 1984--2003."},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"D. Dubhashi and D. Ranjan. 1996. Balls and bins: A study in negative dependence. Random Structures 8 Algorithms 13 2 (1998) 99--124.   D. Dubhashi and D. Ranjan. 1996. Balls and bins: A study in negative dependence. Random Structures 8 Algorithms 13 2 (1998) 99--124.","DOI":"10.1002\/(SICI)1098-2418(199809)13:2<99::AID-RSA1>3.0.CO;2-M"},{"key":"e_1_2_1_9_1","unstructured":"P.\n      Erd\u0151s\n     and \n      L.\n      Lov\u00e1sz\n  . \n  1975\n  . Problems and results on 3-chromatic hypergraphs and some related questions. In Infinite and Finite Sets Vol. \n  11\n   of \n  Colloq\n  . Math. Soc. J. Bolyai. 609--627. \n  North-Holland\n  .  P. Erd\u0151s and L. Lov\u00e1sz. 1975. Problems and results on 3-chromatic hypergraphs and some related questions. In Infinite and Finite Sets Vol. 11 of Colloq. Math. Soc. J. Bolyai. 609--627. North-Holland."},{"key":"e_1_2_1_10_1","unstructured":"Alessandra Graf and Penny Haxell. 2018. Finding independent transversals efficiently. arXiv preprint arXiv:1811.02687.  Alessandra Graf and Penny Haxell. 2018. Finding independent transversals efficiently. arXiv preprint arXiv:1811.02687."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2049697.2049702"},{"key":"e_1_2_1_12_1","unstructured":"D. Harris. 2016. New bounds for the Moser-Tardos distribution. arXiv preprint arXiv:1610.09653.  D. Harris. 2016. New bounds for the Moser-Tardos distribution. arXiv preprint arXiv:1610.09653."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488696"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.57"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3039869"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2017.v013a017"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2014.11.020"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548305007157"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548301004758"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/1365481.1365486"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(03)00031-5"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300000274"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840353"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700379760"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01215349"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585745"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2007.02.003"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1667053.1667060"},{"volume-title":"Proceedings of the 15th International Conference on Integer Programming and Combinatorial Optimization (IPCO\u201911)","author":"Peis B.","key":"e_1_2_1_29_1","unstructured":"B. Peis and A. Wiese . 2011. Universal packet routing with arbitrary bandwidths and transit times . In Proceedings of the 15th International Conference on Integer Programming and Combinatorial Optimization (IPCO\u201911) . 362--375. B. Peis and A. Wiese. 2011. Universal packet routing with arbitrary bandwidths and transit times. In Proceedings of the 15th International Conference on Integer Programming and Combinatorial Optimization (IPCO\u201911). 362--375."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579324"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36694-9_29"},{"key":"e_1_2_1_32_1","series-title":"Lecture Notes in Computer Science","volume-title":"Universal routing strategies for interconnection networks","author":"Scheideler C.","unstructured":"C. Scheideler . 1998. Universal routing strategies for interconnection networks . In Lecture Notes in Computer Science , Vol. 1390 . Springer . C. Scheideler. 1998. Universal routing strategies for interconnection networks. In Lecture Notes in Computer Science, Vol. 1390. Springer."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/S089548019223872X"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-006-0019-9"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(96)00300-7"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3342222","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3342222","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3342222","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:26:00Z","timestamp":1750206360000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3342222"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,8,17]]},"references-count":35,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2019,10,31]]}},"alternative-id":["10.1145\/3342222"],"URL":"https:\/\/doi.org\/10.1145\/3342222","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2019,8,17]]},"assertion":[{"value":"2014-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-08-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}