Dissertation (Metadaten)
Titel:Efficient derandomization of the Lovász Local Lemma and applications to coloring and packing problems
Autor:Nitin Ahuja
Fakultät:Technische Fakultät
DDC Sachgebiet:510 Mathematik
Datum der mdl. Prüfung:19.02.2003
Referent(in):Prof. Dr. Anand Srivastav
Korreferent(en) Korreferentin:Prof. Dr. Klaus Jansen
Beschreibung: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.
Schlagworte:Lovász Local Lemma, Randomized Algorithm, Probabilistic Methods, Approximation Algorithm, Vector Packing, Hypergraph Coloring, Derandomization, Resource Constrained Scheduling
Hypergraph ; Graphfärbung ; Bin-Packing-Problem ; Randomisierter Algorithmus
d923.pdf (737 kB)    ZIP generieren   Details >>