A quasi-PTAS for the two-dimensional geometric knapsack problem

We consider the two-dimensional geometric knapsack problem denned as follows. Given a collection of rectangular axis-parallel items with weights, we want to find a maximum weight subset of the items that can be packed into a rectangular knapsack, i.e., which can be assigned positions within the knapsack such that the items are pair-wise non-overlapping. The goal is to compute the optimal collection of items together with a feasible packing. The problem arises naturally in several applications, and various special cases of the problem have been studied. For the general case the best known result is a (2 +∈)-approximation algorithm, while the only hardness result is NP-hardness. Our main result is a (1 +∈)-approximation algorithm that runs in quasi-polynomial time, provided that the input data consists of (quasi-)polynomially bounded integers. We achieve this result in the setting with and without allowing rotation of the items. Our key technical contribution is to show the existence of a partition for the knapsack into a small number of rectangular boxes. Intuitively, this partition describes the segmentation of the knapsack in some near-optimal solution into large items, areas containing items that are high and thin, and areas containing items that are small and wide. Handling the interaction between these three types of items is a core bottleneck in the design of approximation algorithms for the problem and our partition allows to control this at only marginal cost. In particular, it is so powerful that we do not even need to round the sizes of the items, which is a canonical step in algorithms for geometric knapsack, geometric bin-packing, etc. Finally, we present new algorithms for two-dimensional knapsack and two-dimensional bin-packing under (1 +∈)-resource augmentation with a substantially better running time dependence on e (although at the expense of requiring quasi-polynomial time). The objective value of our computed solutions is as good as the optimum without additional resources. Here we exploit a recent re-suit showing the existence of certain low-complexity low weight separators for sets of non-overlapping rectangles.