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
Author:
Ladewig, Leon
Year:
2021
Document type:
Dissertation
Faculty/School:
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...     »
WWW:
https://mediatum.ub.tum.de/?id=1580033
Date of submission:
09.12.2020
Oral examination:
17.06.2021
File size:
1891497 bytes
Pages:
109
Urn (citeable URL):
https://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:91-diss-20210617-1580033-1-0
Last change:
22.07.2021
 BibTeX