{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:23:42Z","timestamp":1787340222220,"version":"build-2736575974"},"reference-count":36,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2006,1]]},"abstract":"<jats:p>The Lov\u00e1sz local lemma due to Erdo\u02dds and Lov\u00e1sz (Infinite and Finite Sets, Colloq. Math. Soc. J. Bolyai 11, 1975, pp. 609\u2013627) is a powerful tool in proving the existence of rare events. We present an extension of this lemma, which works well when the event to be shown to exist is a conjunction of individual events, each of which asserts that a random variable does not deviate much from its mean. As applications, we consider two classes of NP\u2010hard integer programs: minimax and covering integer programs. A key technique, randomized rounding of linear relaxations, was developed by Raghavan and Thompson (Combinatorica, 7 (1987), pp. 365\u2013374) to derive good approximation algorithms for such problems. We use our extension of the local lemma to prove that randomized rounding produces, with nonzero probability, much better feasible solutions than known before, if the constraint matrices of these integer programs are column\u2010sparse (e.g., routing using short paths, problems on hypergraphs with small dimension\/degree). This complements certain well\u2010known results from discrepancy theory. We also generalize the method of pessimistic estimators due to Raghavan (J. Comput. System Sci., 37 (1988), pp. 130\u2013143), to obtain constructive (algorithmic) versions of our results for covering integer programs.<\/jats:p>","DOI":"10.1137\/s0097539703434620","type":"journal-article","created":{"date-parts":[[2006,11,15]],"date-time":"2006-11-15T22:46:25Z","timestamp":1163630785000},"page":"609-634","source":"Crossref","is-referenced-by-count":19,"title":["An Extension of the Lov\u00e1sz Local Lemma, and its Applications to Integer Programming"],"prefix":"10.1137","volume":"36","author":[{"given":"Aravind","family":"Srinivasan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,9,21]]},"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":"publisher","DOI":"10.1016\/0196-6774(86)90019-2"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"N. Alon and J. H. Spencer,\n                      The Probabilistic Method\n                      , 2nd ed., John Wiley and Sons, New York, 2000.","DOI":"10.1002\/0471722154"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240020402"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(81)90022-6"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1007\/BF02591800"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1145\/115234.115347"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(1999010)14:1<87::AID-RSA5>3.0.CO;2-O"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1287\/moor.4.3.233"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"A. Czumaj and C. Scheideler,\n                      An 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, Portland, OR, 2000, pp. 38\u201347.","DOI":"10.1145\/335305.335310"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1287\/moor.7.4.515"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/0603059"},{"key":"R14","unstructured":"P. Erdo\u02dds and L. Lov\u00e1sz,\n                      Problems and results on 3\u2010chromatic hypergraphs and some related questions\n                      , Infinite and Finite Sets, A. Hajnal et al., eds., Colloq. Math. Soc. J. Bolyai 11, North\u2010Holland, Amsterdam, 1975, pp. 609\u2013627."},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1007\/BF01651330"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1007\/BF00403406"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(87)90026-5"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840353"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"S. G. Kolliopoulos and N. E. Young,\n                      Tight approximation results for general covering integer programs\n                      , in Proceedings of the IEEE Symposium on Foundations of Computer Science, Las Vegas, 2001, pp. 522\u2013528.","DOI":"10.1109\/SFCS.2001.959928"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700379760"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"F. T. Leighton, S. B. Rao, and A. Srinivasan,\n                      Multicommodity flow and circuit switching\n                      , in Proceedings of the Hawaii International Conference on System Sciences, Kohala Coast, HI, 1998, pp. 459\u2013465.","DOI":"10.1109\/HICSS.1998.649241"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(75)90058-8"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1137\/0215074"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"M. Molloy and B. Reed,\n                      Further algorithmic aspects of the local lemma\n                      , in Proceedings of the ACM Symposium on Theory of Computing, Dallas, 1998, pp. 524\u2013529.","DOI":"10.1145\/276698.276866"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"M. Molloy and B. Reed,\n                      Graph Coloring and the Probabilistic Method\n                      , Springer\u2010Verlag, Berlin, 2002.","DOI":"10.1007\/978-3-642-04016-0"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80069-8"},{"key":"R27","doi-asserted-by":"crossref","unstructured":"R. Motwani and P. Raghavan,\n                      Randomized Algorithms\n                      , Cambridge University Press, Cambridge, UK, 1995.","DOI":"10.1017\/CBO9780511814075"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305237"},{"key":"R29","doi-asserted-by":"crossref","unstructured":"C. H. Papadimitriou and M. Yannakakis,\n                      On the approximability of trade\u2010offs and optimal access of web sources\n                      , in Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science, Redondo Beach, 2000, pp. 86\u201392.","DOI":"10.1109\/SFCS.2000.892068"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1287\/moor.20.2.257"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90003-7"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579324"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1137\/S089548019223872X"},{"key":"R34","unstructured":"J. H. Spencer,\n                      Ten Lectures on the Probabilistic Method\n                      , SIAM, Philadelphia, 1987."},{"key":"R35","unstructured":"A. Srinivasan,\n                      An extension of the Lov\u00e1sz Local Lemma, and its applications to integer programming\n                      , in Proceedings of the Seventh Annual ACM\u2010SIAM Symposium on Discrete Algorithms, Atlanta, 1996, pp. 6\u201315."},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796314240"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539703434620","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:25:41Z","timestamp":1787336741000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539703434620"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,1]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2006,1]]}},"alternative-id":["10.1137\/S0097539703434620"],"URL":"https:\/\/doi.org\/10.1137\/s0097539703434620","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,1]]}}}