Dissertation (Metadaten)
Titel:Approximation algorithms for 2d packing problems
Autor:Olga Gerber
Fakultät:Technische Fakultät
DDC Sachgebiet:510 Mathematik
Datum der mdl. Prüfung:18.10.2005
Referent(in):Prof. Dr. Klaus Jansen
Korreferent(en) Korreferentin:Prof. Dr. Anand Srivastav
Beschreibung:In this thesis we address such 2-dimensional packing problems as strip packing, bin packing and storage packing. These problems play an important role in many application areas, e.g. cutting stock, VLSI design, image processing, and multiprocessor scheduling. The larger part of work is devoted to the storage packing problem, that is the problem of packing weighted rectangles into a single rectangle so as to maximize the total weight of the packed rectangles. Despite the practical importance of the problem, there are just few known results in the literature. The main objective was to fill this gap and also to build the bridges to already known algorithmic solutions for strip packing and bin packing problems. This was successfully achieved. Considering natural relaxations of the storage packing problem we proposed a number of efficient algorithms which are able to find solutions within a factor of (1-\epsilon) of the optimum in polynomial time.
Schlagworte:approximation, packing, storage packing, storage minimization, rectangle packing, strip packing , resource augmentation, unit square, large resources
Zweidimensionales Packungsproblem ; Approximationsalgorithmus
d1671.pdf (768 kB)    ZIP generieren   Details >>