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.