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
 Art des Abschluß: Doktorarbeit

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle

einblenden: