Approximation Algorithms for Rectangle Packing Problems

You are cordially invited to attend the PhD Dissertation Defense of Salvatore INGALA on Friday, October 27th 2017 at 16h30 in room SI-003 (Informatics building) 

Abstract:
In rectangle packing problems we are given the task of positioning some axis-aligned rectangles inside a given plane region, so that they do not overlap with each other. In the Maximum Weight Independent Set of Rectangles (MWISR) problem, their position is already fixed and we can only select which rectangles to choose, while trying to maximize their total weight. In the Strip Packing problem, we have to pack all the given rectangles in a rectangular region of fixed width, while minimizing its height. In the 2-Dimensional Geometric Knapsack (2DGK) problem, 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. All of the above problems are NP-hard, and a lot of research has approached them by trying to find efficient approximation algorithms. Besides their intrinsic interest as natural mathematical problems, geometric packing has numerous applications in settings like map labeling, resource allocation, data mining, cutting stock, VLSI design, advertisement placement, and so on. We study a generalization of MWISR and use it to obtain improved approximation algorithms for a resource allocation problem called bagUFP. We revisit some classical results on Strip Packing 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 and cleaner algorithms that work unchanged for different problems. In this framework, we obtain improved approximation algorithms for a variant of Strip Packing where one is allowed pseudo-polynomial time, and for a variant of 2DGK where one is allowed to rotate the given rectangles by 90° (thereby swapping width and height). For the latter, we propose the first algorithms with approximation factor better than 2. For the main variant of 2DGK (without 90° 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 + ε)-approximation for this problem and exploiting the combinatorial structure of the 2DGK problem, we obtain the first algorithms that break the barrier of 2 for the approximation factor of this problem.

Dissertation Committee:

• Prof. Luca Maria Gambardella, IDSIA-Dalle Molle Institute for Artificial Intelligence, Switzerland (Research Advisor)
• Prof. Fabrizio Grandoni, IDSIA-Dalle Molle Institute for Artificial Intelligence, Switzerland (Research co-Advisor)
• Prof. Antonio Carzaniga, Università della Svizzera italiana, Switzerland (Internal Member)
• Prof. Evanthia Papadopoulou, Università della Svizzera italiana, Switzerland (Internal Member)
• Prof. Bansal Nikhil, Eindhoven University of Technology, Netherlands (External Member)
• Prof. Roberto Grossi, University of Pisa, Italy (External Member)