English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Thesis

A Tale of Two Packing Problems: Improved Algorithms and Tighter Bounds for Online Bin Packing and the Geometric Knapsack Problem

MPS-Authors
/persons/resource/persons79285

Heydrich,  Sandy
Algorithms and Complexity, MPI for Informatics, Max Planck Society;
International Max Planck Research School, MPI for Informatics, Max Planck Society;

Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available
Citation

Heydrich, S. (2018). A Tale of Two Packing Problems: Improved Algorithms and Tighter Bounds for Online Bin Packing and the Geometric Knapsack Problem. PhD Thesis, Universität des Saarlandes, Saarbrücken. doi:10.22028/D291-27240.


Cite as: https://hdl.handle.net/21.11116/0000-0001-E3DC-7
Abstract
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.