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. For bin packing, we revisit a well-known algorithm and present several improved bounds.     «

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....     »

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 wir neue Algorithmen vor und bewerten diese anhand ihrer Kompetitivität. Für das Binpacking-Problem greifen wir einen klassischen Algorithmus auf und präsentieren verbesserte Schranken.     «

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...     »