Approximation algorithms for 2d packing problems

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.

Vorschau

Rechte

Nutzung und Vervielfältigung:

Keine Lizenz. Es gelten die Bestimmungen des deutschen Urheberrechts (UrhG).

Bitte beachten Sie, dass einzelne Bestandteile der Publikation anderweitigen Lizenz- bzw. urheberrechtlichen Bedingungen unterliegen können.

Zitieren

Zitierform:
Zitierform konnte nicht geladen werden.