A new algorithm approach to the general Lovász local lemma with applications to scheduling and satisfiability problems (extended abstract)
Artur Czumaj, Christian Scheideler · 2000
The LovAsz Local Lemma (LLL) is a powerful tool that is increasingly playing a valuable role in computer science.It has led to solutions for numerous problems in many different areas, reaching from problems in pure combinatorics to problems in routing, scheduling and approximation theory.However, since the original lemma is non-constructive, many of these solutions were first purely existential.A breakthrough result by Beck and its generalizations have led to polynomial time algorithms for many ~f these problems.However, these methods can only be applied to a simple, symmetric form of the LLL.In this paper we provide a novel approach to design polynomial-time algorithms for problems that require the LLL in its general form.We apply our techniques to find good approximate solutions to a large class of NP-hard problems called minimax integer programs (MIPs).Our method finds approximate solutions that are --especially for problems of non-uniform character --significantly better than all methods presented before.To demonstrate the applicability of our approach, we apply it to transform important results in the area of job shop scheduling that have so far been only existential (due to the fact that the general LLL was used) into algorithms that find the predicted solutions (with only a small loss) in polynomial time.Fhrthermore, ¢Work partly done while the author was with Heinz Nixdorf Institute and Department of Mathematics and Computer Science at