Efficient derandomization of the Lovász Local Lemma and applications to coloring and packing problems

Ahuja, Nitin

We use algorithmic versions of Lovasz Local Lemma (LLL) to deal with the following two packing type problems: (i) a particular kind of hypergraph coloring problem, and (ii) vector packing problem. The hypergraph coloring problem is connected to the resource constrained scheduling problem and vector packing is a particular multi-dimensional generalization of the well known bin packing problem. The randomized algorithms yielding better results for the above mentioned problems are then efficiently derandomized.

Preview

Cite

Citation style:

Ahuja, Nitin: Efficient derandomization of the Lovász Local Lemma and applications to coloring and packing problems. 2003.

Rights

Use and reproduction:
No CC License (german copyright law applies)

Export