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.},\n}\n'