2003/07/18 by Aravind Srinivasan, Srinivasan, Aravind · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #F.1.2 #F.2.2 #FOS: Computer and information sciences #G.2.2 #G.3 #Machine Learning and Algorithms #Optimization and Search Problems #cs.DS
paper · pdf · doi:10.48550/arxiv.cs/0307043
22 pages, preliminary version appeared in the SODA 1996 conference
arxiv created 2003/07/18 · openalex publication_date 2003/07/18 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Lovasz Local Lemma due to Erdos and Lovasz 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-hard integer programs: minimax and covering integer programs. A key technique, randomized rounding of linear relaxations, was developed by Raghavan and Thompson to derive good approximation algorithms for such problems. We use our extension of the Local Lemma to prove that randomized rounding produces, with non-zero probability, much better feasible solutions than known before, if the constraint matrices of these integer programs are column-sparse (e.g., routing using short paths, problems on hypergraphs with small dimension/degree). This complements certain well-known results from discrepancy theory. We also generalize the method of pessimistic estimators due to Raghavan, to obtain constructive (algorithmic) versions of our results for covering integer programs.