An Extension of the Lovász Local Lemma, and its Applications to Integer Programming
- 1 January 2006
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 36 (3), 609-634
- https://doi.org/10.1137/s0097539703434620
Abstract
No abstract availableAll Related Versions
This publication has 25 references indexed in Scilit:
- Static and Dynamic Path Selection on Expander Graphs: A Random Walk ApproachRandom Structures & Algorithms, 1999
- The strong chromatic number of a graphRandom Structures & Algorithms, 1992
- A parallel algorithmic version of the local lemmaRandom Structures & Algorithms, 1991
- An algorithmic approach to the Lovász local lemma. IRandom Structures & Algorithms, 1991
- Simulating (log c n )-wise independence in NCJournal of the ACM, 1991
- A fast and simple randomized parallel algorithm for the maximal independent set problemJournal of Algorithms, 1986
- Integral approximation sequencesMathematical Programming, 1984
- Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative DataMathematics of Operations Research, 1982
- “Integer-making” theoremsDiscrete Applied Mathematics, 1981
- A Greedy Heuristic for the Set-Covering ProblemMathematics of Operations Research, 1979