  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.
