Approximation Algorithms for Two-dimensional Geometric Packing Problems

You are cordially invited to attend the PhD Dissertation Defense of Waldo Gálvez on Monday October 14th, 2019 at 13:30 in room A-33 (Red building).

Abstract:
There are a lot of natural problems arising in real life that can be modeled as discrete optimization problems. Unfortunately many of them are believed to be hard to solve efficiently (i.e. they cannot be solved in polynomial time unless P=NP). An approximation algorithm is one of the ways to tackle these hard optimization problems. These algorithms have polynomial running time and guarantee a feasible solution whose value is within a proven factor of the optimal solution value. The field of approximation algorithms has grown fast over the last few decades, and many techniques have been developed to handle these hard problems. However, there are still many problems for which substantial progress is needed. The ultimate goal for any optimization problem is an approximation algorithm with a performance guarantee along with a matching hardness of approximation result. In this thesis we address two fundamental geometric packing problems: Strip Packing and Two-dimensional Geometric Knapsack. In the Strip Packing problem we are given a set of rectangles and the goal is to place them into a rectangular region of fixed width W so that they do not overlap while minimizing the total height of the spanned region. On the other hand, in the Two-dimensional Geometric Knapsack problem we are given a set of rectangles with associated profits and a square region of fixed height and width N, and the goal is to select and pack inside the region a subset of the rectangles of maximum profit so that they do not overlap. Both problems are NP-hard and have many interesting real-world applications, so they have been studied through the lens of approximation algorithms in the past. We start by describing our results on the Strip Packing problem, where we develop improved approximation algorithms for some important special cases. In the first case we show a pseudo-polynomial time (PPT) (4/3+eps)-approximation which improves and simplifies the previous best (7/5+eps)-approximation from Nadiradze & Wiese [SODA 2016]. In the second case we show that there exists a tight (3/2+eps)-approximation for the problem in the special case where no rectangle is "large" in both dimensions (compared to the dimensions of the optimal solution). Both these results try to give new insights in order to approach the important open problem of improving the approximability of Strip Packing. In the second part we describe our results for the Two-dimensional Geometric Knapsack problem and some of their known variants. For this problem we improve upon the best known approximation ratios for the cases with and without 90 degree rotations, and give refined approximation algorithms for the case of uniform weights. These are the first algorithms that break the approximation barrier of 2 for the aforementioned problems. As an important development we introduce the notion of L-packings which turns out to be crucial to achieve the previously mentioned results in the settings without rotations, and may be of independent interest to address related problems.

Dissertation Committee:
- Prof. Fabrizio Grandoni, Università della Svizzera italiana, Switzerland (Research Advisor)
- Prof. Antonio Carzaniga, Università della Svizzera italiana, Switzerland (Internal Member)
- Prof. Stefan Wolf, Università della Svizzera italiana, Switzerland (Internal Member)
- Prof. Jose R. Correa, Universidad de Chile, Chile (External Member)
- Prof. Alberto Marchetti-Spaccamela, Università "La Sapienza" Rome, Italy (External Member)