{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:40:22Z","timestamp":1787337622575,"version":"build-2736575974"},"reference-count":25,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2001,1]]},"abstract":"<jats:p>The Lov\u00e1sz local lemma (LLL) is a powerful tool that is increasingly playing a valuable role in computer science. The original lemma was nonconstructive; a breakthrough of Beck and its generalizations (due to Alon and Molloy and Reed) have led to constructive versions. However, these methods do not capture some classes of applications of the LLL. We make progress on this by providing algorithmic approaches to two families of applications of the LLL. The first provides constructive versions of certain applications of an extension of the LLL (modeling, e.g., hypergraph-partitioning and low-congestion routing problems); the second provides new algorithmic results on constructing disjoint paths in graphs. Our results can also be seen as constructive upper bounds on the integrality gap of certain packing problems. One common theme of our work is a \"gradual rounding\" approach.<\/jats:p>","DOI":"10.1137\/s0097539700379760","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"626-641","source":"Crossref","is-referenced-by-count":24,"title":["New Algorithmic Aspects of the Local Lemma with Applications to Routing and Partitioning"],"prefix":"10.1137","volume":"31","author":[{"given":"Tom","family":"Leighton","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chi-Jen","family":"Lu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Satish","family":"Rao","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aravind","family":"Srinivasan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,27]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240020403"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240030102"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"Michael Molloy, The probabilistic method, Algorithms Combin., Vol. 16, Springer, Berlin, 1998, 1\u2013352001a:05135","DOI":"10.1007\/978-3-662-12788-9_1"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240020402"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177729330"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"A. Czumaj and C. Scheideler,\n                      A new algorithmic approach to the general Lov\u00e1sz local lemma with applications to scheduling and satisfiability problems\n                      , in Proceedings of the ACM Symposium on Theory of Computing, ACM, Portland, OR, 2000, pp. 38\u201347.","DOI":"10.1145\/335305.335310"},{"key":"R7","unstructured":"P. Erd\u00f6s and L. Lov\u00e1sz,\n                      Problems and results on 3\u2010chromatic hypergraphs and some related questions\n                      , in Infinite and Finite Sets, A. Hajnal et al., eds., Colloq. Math. Soc. J\u00e1nos Bolyai 11, North Holland, Amsterdam, 1975, pp. 609\u2013627."},{"key":"R8","unstructured":"Alan Frieze, Edge\u2010disjoint paths in expander graphs, ACM, New York, 2000, 717\u20137251755532"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1007\/BF00403406"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"R11","unstructured":"J. Kleinberg,\n                      Approximation Algorithms for Disjoint Paths Problems\n                      , Ph.D. thesis, Department of EECS, MIT, 1996."},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(87)90026-5"},{"key":"R13","volume-title":"The art of computer programming. Vol. 2","author":"Knuth Donald","year":"1981"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"F. T. Leighton, S. B. Rao, and A. Srinivasan,\n                      Multi\u2010commodity flow and circuit switching\n                      , in Proc. Hawaii International Conference on System Sciences, 1998, pp. 459\u2013465.","DOI":"10.1109\/HICSS.1998.649241"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(85)90004-6"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"Chi\u2010Jen Lu, Deterministic hypergraph coloring and its applications, Lecture Notes in Comput. Sci., Vol. 1518, Springer, Berlin, 1998, 35\u2013461729160","DOI":"10.1007\/3-540-49543-6_4"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1007\/BF01202792"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"Michael Molloy, Bruce Reed, Further algorithmic aspects of the local lemma, ACM, New York, 1999, 524\u20135291715600","DOI":"10.1145\/276698.276866"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"R. Motwani and P. Raghavan,\n                      Randomized Algorithms\n                      , Cambridge University Press, 1995.","DOI":"10.1017\/CBO9780511814075"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90003-7"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579324"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1137\/S089548019223872X"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-42.1.178"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"Joel Spencer, The probabilistic lens: Sperner, Tur\u00e1n and Bregman revisited, Cambridge Univ. Press, Cambridge, 1990, 391\u201339692i:05127","DOI":"10.1017\/CBO9780511983917.033"},{"key":"R25","unstructured":"Aravind Srinivasan, An extension of the Lov\u00e1sz local lemma, and its applications to integer programming, ACM, New York, 1996, 6\u20131597b:90080"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539700379760","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:21:38Z","timestamp":1787336498000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539700379760"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,1]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2001,1]]}},"alternative-id":["10.1137\/S0097539700379760"],"URL":"https:\/\/doi.org\/10.1137\/s0097539700379760","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2001,1]]}}}