Approximating Geometric Knapsack via L-packings

We study the two-dimensional geometric knapsack problem (2DK), a geometric variant of the classical knapsack problem. In this problem we are given a set of axis-aligned rectangular items, each one with an associated profit, and an axis-aligned square knapsack. The goal is to find a (non-overlapping) packing of a maximum profit subset of items inside the knapsack without rotating items. This is a very well-studied optimization problem and finds applications in scheduling, memory allocation, advertisement placement etc. The best-known polynomial-time approximation factor for this problem (even just in the cardinality case) is $2+\eps$ [Jansen and Zhang, SODA 2004].

After more than a decade, in this paper we break the 2-approximation barrier, achieving a polynomial-time $17/9+\eps<1.89$ approximation, which improves to $558/325+\eps<1.72$ in the cardinality case. We also consider the variant of the problem with rotations (2DKR) , where the items can be rotated by $90$ degrees. Also in this case the best-known polynomial-time approximation factor (even for the cardinality case) is $2+\eps$ [Jansen and Zhang, SODA 2004]. Exploiting part of the machinery developed for 2DK plus a few additional ideas, we obtain a polynomial-time $3/2+\eps$-approximation for 2DKR, which improves to $4/3+\eps$ in the cardinality case (joint work with Waldo Galvez, Fabrizio Grandoni, Sandy Heydrich, Salvatore Ingala and Andreas Wiese. This result will appear in FOCS 2017).

Bio: Arindam Khan is a researcher in IDSIA, SUPSI in Lugano, Switzerland. His research areas include approximation algorithms, online algorithms and computational geometry. He has obtained his PhD in Algorithms, Combinatorics and Optimization (ACO) from Georgia Institute of Technology, Atlanta, USA under Prof. Prasad Tetali.  Previously he has been a research intern in Theory group, Microsoft Research Redmond and Microsoft Research Silicon Valley USA, a visiting researcher at Simons Institute, Berkeley, USA and a blue scholar in IBM Research India.