Diese Arbeit untersucht Schedulingprobleme in zwei Szenarien. Der erste Abschnitt betrifft die Aufgabe, die Kontenmenge eines Hypergraphen in Teile gleicher Größe zu partitionieren. Diese Frage stellt sich bei der Lastverteilung auf parallelen Systemen. Die Arbeit untersucht die Berechnungskomplexität derartiger Probleme und zeigt neue Approximationsalgorithmen. Im zweiten Abschnitt der Arbeit wird ein Online-Algorithmus für das verallgemeinerte Sortierpufferproblem entwickelt, der einen polylogarithmischen kompetitiven Faktor erreicht.     «

Diese Arbeit untersucht Schedulingprobleme in zwei Szenarien. Der erste Abschnitt betrifft die Aufgabe, die Kontenmenge eines Hypergraphen in Teile gleicher Größe zu partitionieren. Diese Frage stellt sich bei der Lastverteilung auf parallelen Systemen. Die Arbeit untersucht die Berechnungskomplexität derartiger Probleme und zeigt neue Approximationsalgorithmen. Im zweiten Abschnitt der Arbeit wird ein Online-Algorithmus für das verallgemeinerte Sortierpufferproblem entwickelt, der einen polylog...     »