User: Guest  Login
If you experience problems opening the document, please try this link.
Original title:
Scheduling algorithms for parallel processing and buffering problems
Translated title:
Schedulingalgorithmen für parallele Systeme und Pufferprobleme
Author:
Stotz, Hermann Wilhelm Richard
Year:
2020
Document type:
Dissertation
Faculty/School:
Fakultät für Informatik
Advisor:
Räcke, Harald (Prof. Dr.)
Referee:
Räcke, Harald (Prof. Dr.); Röglin, Heiko (Prof. Dr.)
Language:
en
Subject group:
DAT Datenverarbeitung, Informatik
TUM classification:
DAT 500d
Abstract:
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.
Translated abstract:
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...     »
WWW:
https://mediatum.ub.tum.de/?id=1538397
Date of submission:
24.02.2020
Oral examination:
30.07.2020
File size:
990009 bytes
Pages:
134
Urn (citeable URL):
https://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:91-diss-20200730-1538397-1-9
Last change:
06.09.2021
 BibTeX