Computer Science – Data Structures and Algorithms
Scientific paper
2003-07-18
Computer Science
Data Structures and Algorithms
22 pages, preliminary version appeared in the SODA 1996 conference
Scientific paper
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.
No associations
LandOfFree
An Extension of the Lovasz Local Lemma, and its Applications to Integer Programming does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with An Extension of the Lovasz Local Lemma, and its Applications to Integer Programming, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Extension of the Lovasz Local Lemma, and its Applications to Integer Programming will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-489289