Title: Approximation Algorithms for Rectangle Packing Problems (PhD Thesis),
Abstract: In rectangle packing problems we are given the task of placing axis-aligned
rectangles in a given plane region, so that they do not overlap with each
other. In Maximum Weight Independent Set of Rectangles (MWISR), their position
is given and we can only select which rectangles to choose, while trying to
maximize their total weight. In Strip Packing (SP), we have to pack all the
given rectangles in a rectangular region of fixed width, while minimizing its
height. In 2-Dimensional Geometric Knapsack (2DGK), the target region is a
square of a given size, and our goal is to select and pack a subset of the
given rectangles of maximum weight. We study a generalization of MWISR and use
it to improve the approximation for a resource allocation problem called
bagUFP. We revisit some classical results on SP and 2DGK, by proposing a
framework based on smaller containers that are packed with simpler rules; while
variations of this scheme are indeed a standard technique in this area, we
abstract away some of the problem-specific differences, obtaining simpler
algorithms that work for different problems. We obtain improved approximations
for SP in pseudo-polynomial time, and for a variant of 2DGK where one can to
rotate the rectangles by 90°. For the latter, we propose the first
algorithms with approximation factor better than 2. For the main variant of
2DGK (without rotations), a container-based approach seems to face a natural
barrier of 2 in the approximation factor. Thus, we consider a generalized kind
of packing that combines container packings with another packing problem that
we call L-packing problem, where we have to pack rectangles in an L-shaped
region of the plane. By finding a (1 + {\epsilon})-approximation for this
problem and exploiting the combinatorial structure of 2DGK, we obtain the first
algorithms that break the barrier of 2 for the approximation factor of this
problem.