Approximation Schemes and Structural Barriers for the Two-Dimensional Knapsack Problem with Rotations

We study the two-dimensional (geometric) knapsack problem with rotations (2DKR), in which we are given a square knapsack and a set of rectangles with associated profits. The objective is to find a maximum profit subset of rectangles that can be packed without overlap in an axis-aligned manner, possibly by rotating some rectangles by 90 • . The best-known polynomial time algorithm for the problem has an approximation ratio of 3/2 + ϵ for any constant ϵ > 0, with an improvement to 4/3 + ϵ in the cardinality case, due to Gálvez, Grandoni, Heydrich, Ingala, Khan, and Wiese (FOCS 2017, TALG 2021). Obtaining a PTAS for the problem, even in the cardinality case, has remained a major open question in the setting of multidimensional packing problems, as mentioned in the survey by Christensen, Khan, Tetali, and Pokutta (Computer Science Review, 2017).

In this paper, we present a PTAS for the cardinality case of 2DKR. In contrast to the setting without rotations, we show that there are (1 + ϵ)-approximate solutions in which all items are packed greedily inside a constant number of rectangular containers. Our result is based on a new resource contraction lemma, which might be of independent interest. With our techniques, we also obtain a (1 + ϵ)approximation algorithm in the weighted case when all given items are skewed, i.e., each of them has sufficiently small height or sufficiently small width. In contrast, for the general weighted case, we prove that this simple type of packing is not sufficient to obtain a better approximation ratio than 1.5. However, we break this structural barrier and design a (1.497 + ϵ)-approximation algorithm for 2DKR in the weighted case. Our arguments also improve the best-known approximation ratio for the (weighted) case without rotations to 13/7 + ϵ ≈ 1.857 + ϵ.

Finally, we establish a lower bound of n Ω(1/ϵ) on the running time of any (1 + ϵ)-approximation algorithm for our problem with or without rotations -even in the cardinality setting, assuming the k-SUM Conjecture. In particular, this shows that an approximation scheme for the case of rectangles of two-dimensional geometric knapsack requires much more running time than for the case of squares.