User: Guest  Login
Original title:
Online Algorithms for Packing Problems in the Random-Order Model 
Translated title:
Online-Algorithmen für Packungsprobleme im Random-Order-Modell 
Year:
2021 
Document type:
Dissertation 
Institution:
Fakultät für Informatik 
Advisor:
Albers, Susanne (Prof. Dr.) 
Referee:
Albers, Susanne (Prof. Dr.); Kesselheim, Thomas (Prof. Dr.) 
Language:
en 
Subject group:
DAT Datenverarbeitung, Informatik 
Keywords:
online algorithms, random-order model, combinatorial optimization 
Translated keywords:
Online-Algorithmen, Random-Order-Modell, kombinatorische Optimierung 
TUM classification:
DAT 500 
Abstract:
In this thesis, we study online algorithms for different packing problems from the field of combinatorial optimization. As considering fully adversarial inputs leads to strong impossibility results for most of these problems, we consider the random-order model. This model is an alternative to pure worst-case analysis and became increasingly popular over the past years. For the k-secretary problem and the knapsack problem, we propose new algorithms and evaluate them in terms of competitive ratio....    »
 
Translated abstract:
In dieser Arbeit untersuchen wir Online-Algorithmen für verschiedene Packungsprobleme aus dem Gebiet der kombinatorischen Optimierung. Da die Betrachtung von vollständig gegnerischen Eingaben zu starken Negativresultaten bei den meisten dieser Probleme führt, betrachten wir das Random-Order-Modell. Dieses Modell stellt eine Alternative zu Worst-Case-Analysen dar und hat sich über die letzten Jahre zunehmender Beliebtheit erfreut. Für das k-Secretary-Problem und für das Rucksackproblem stellen wi...    »
 
Oral examination:
17.06.2021 
File size:
1891497 bytes 
Pages:
109 
Last change:
22.07.2021