Dissertation (Metadaten)
Titel:Efficient derandomization of the Lovász Local Lemma and applications to coloring and packing problems
 
Autor:Nitin Ahuja
 
URN:NBN:urn:nbn:de:gbv:8-diss-9232
 
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
 
Dokumente:
d923.pdf (737 kB)    ZIP generieren   Details >>