Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

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

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.

Item is

Basisdaten

einblenden: ausblenden:
Genre: Hochschulschrift

Externe Referenzen

einblenden:
ausblenden:
Beschreibung:
-
OA-Status:
Grün

Urheber

einblenden:
ausblenden:
 Urheber:
Heydrich, Sandy1, 2, Autor           
van Stee, Rob1, Ratgeber           
Mehlhorn, Kurt1, Gutachter           
Grandoni, Fabrizio3, Gutachter           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2International Max Planck Research School, MPI for Informatics, Max Planck Society, Campus E1 4, 66123 Saarbrücken, DE, ou_1116551              
3Discrete Optimization, MPI for Informatics, Max Planck Society, ou_1116548              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: 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.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2018-06-122018-08-062018
 Publikationsstatus: Erschienen
 Seiten: viii, 161 p.
 Ort, Verlag, Ausgabe: Saarbrücken : Universität des Saarlandes
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: BibTex Citekey: Heydrphd18
DOI: 10.22028/D291-27240
URN: urn:nbn:de:bsz:291-scidok-ds-272400
Anderer: hdl:20.500.11880/27141
 Art des Abschluß: Doktorarbeit

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle

einblenden: