@phdthesis{Heydrphd18,
TITLE = {A Tale of Two Packing Problems: Improved Algorithms and Tighter Bounds for Online Bin Packing and the Geometric Knapsack Problem},
AUTHOR = {Heydrich, Sandy},
LANGUAGE = {eng},
URL = {urn:nbn:de:bsz:291-scidok-ds-272400},
DOI = {10.22028/D291-27240},
SCHOOL = {Universit{\"a}t des Saarlandes},
ADDRESS = {Saarbr{\"u}cken},
YEAR = {2018},
DATE = {2018},
ABSTRACT = {Abstract<br>In this thesis, we deal with two packing problems: the online bin packing<br>and the geometric knapsack problem. In online bin packing, the aim is to pack<br>a given number of items of dierent size into a minimal number of containers.<br>The items need to be packed one by one without knowing future items. For<br>online bin packing in one dimension, we present a new family of algorithms<br>that constitutes the rst improvement over the previously best algorithm in<br>almost 15 years. While the algorithmic ideas are intuitive, an elaborate analysis<br>is required to prove its competitive ratio. We also give a lower bound for the<br>competitive ratio of this family of algorithms. For online bin packing in higher<br>dimensions, we discuss lower bounds for the competitive ratio and show that the<br>ideas from the one-dimensional case cannot be easily transferred to obtain better<br>two-dimensional algorithms.<br>In the geometric knapsack problem, one aims to pack a maximum weight<br>subset of given rectangles into one square container. For this problem, we consider<br>oine approximation algorithms. For geometric knapsack with square items,<br>we improve the running time of the best known<br>PTAS<br>and obtain an<br>EPTAS<br>.<br>This shows that large running times caused by some standard techniques for<br>geometric packing problems are not always necessary and can be improved.<br>Finally, we show how to use resource augmentation to compute optimal solutions<br>in<br>EPTAS<br>-time, thereby improving upon the known<br>PTAS for this case.},
}