text: 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.
  @cite_5: 
  @cite_22: We study the relation between a class of 0–1 integer linear programs and their rational relaxations. We give a randomized algorithm for transforming an optimal solution of a relaxed problem into a provably good solution for the 0–1 problem. Our technique can be a of extended to provide bounds on the disparity between the rational and 0–1 optima for a given problem instance.
  @cite_20: We consider the problem of approximating an integer program by first solving its relaxation linear program and "rounding" the resulting solution. For several packing problems, we prove probabilistically that there exists an integer solution close to the optimum of the relaxation solution. We then develop a methodology for converting such a probabilistic existence proof to a deterministic approximation algorithm. The methodology mimics the existence proof in a very strong sense.
summary: Given an ILP, we can find an optimal solution @math to its LP relaxation efficiently, but need to round fractional entries in @math to integers. The idea of randomized rounding is: given a real @math , round @math to @math with probability @math , and round @math to @math with probability @math . This has the nice property that the mean outcome is @math . Starting with this idea, the analysis of @cite_22 produces an integral solution of value at most @math for MIPs (though phrased a bit differently); this is derandomized in @cite_20 . But this does not exploit the sparsity of @math ; the previously-mentioned result of @cite_5 produces an integral solution of value at most @math .