Approximating Geometric Knapsack via L-packings

Arindam Khan
Jaikumar Radhakrishnan
Thursday, 24 Aug 2017, 16:00 to 17:00
A-201 (STCS Seminar Room)
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+\epsilon$ [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+\epsilon