非表示:
キーワード:
-
要旨:
Abstract
In this thesis, we deal with two packing problems: the online bin packing
and the geometric knapsack problem. In online bin packing, the aim is to pack
a given number of items of dierent size into a minimal number of containers.
The items need to be packed one by one without knowing future items. For
online bin packing in one dimension, we present a new family of algorithms
that constitutes the rst improvement over the previously best algorithm in
almost 15 years. While the algorithmic ideas are intuitive, an elaborate analysis
is required to prove its competitive ratio. We also give a lower bound for the
competitive ratio of this family of algorithms. For online bin packing in higher
dimensions, we discuss lower bounds for the competitive ratio and show that the
ideas from the one-dimensional case cannot be easily transferred to obtain better
two-dimensional algorithms.
In the geometric knapsack problem, one aims to pack a maximum weight
subset of given rectangles into one square container. For this problem, we consider
oine approximation algorithms. For geometric knapsack with square items,
we improve the running time of the best known
PTAS
and obtain an
EPTAS
.
This shows that large running times caused by some standard techniques for
geometric packing problems are not always necessary and can be improved.
Finally, we show how to use resource augmentation to compute optimal solutions
in
EPTAS
-time, thereby improving upon the known
PTAS for this case.
