Treffer: Scheduling algorithms for parallel processing and buffering problems ; Schedulingalgorithmen für parallele Systeme und Pufferprobleme

In this work, we analyze scheduling problems in two scenarios. First, we consider the problem of partitioning the vertex set of a hypergraph into parts of equal size. This problem derives its importance from load balancing in parallel systems. We explore the computational complexity of hypergraph partitioning and develop new approximation algorithms. Second, we study Generalized Reordering Buffer Management and present an online algorithm of polylogarithmic competitive ratio for this problem. ; 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.