Approximating the Geometric Knapsack Problem in Near-Linear Time and Dynamically

An important goal in algorithm design is determining the best running time for solving a problem (approximately). For some problems, we know the optimal running time, assuming certain conditional lower bounds. In this work, we study the d-dimensional geometric knapsack problem where we are far from this level of understanding. We are given a set of weighted d-dimensional geometric items like squares, rectangles, or hypercubes and a knapsack which is a square or a (hyper-) cube. We want to select a subset of items that fit non-overlappingly inside the knapsack, maximizing the total profit of the packed items. We make a significant step towards determining the best running time for solving these problems approximately by presenting approximation algorithms with near-linear running times for any constant dimension d and any constant parameter. For (hyper) -cubes, we present a (1+) -approximation algorithm whose running time drastically improves upon the known (1+) -approximation algorithm which has a running time where the exponent of n depends exponentially on 1/ and d. Moreover, we present a (2+) -approximation algorithm for rectangles in the setting without rotations and a (17/9+) -approximation algorithm if we allow rotations by 90 degrees. The best known polynomial time algorithms for these settings have approximation ratios of 17/9+ and 1. 5+, respectively, and running times in which the exponent of n depends exponentially on 1/. We also give dynamic algorithms with polylogarithmic query and update times and the same approximation guarantees as the algorithms above. Key to our results is a new family of structured packings which we call easily guessable packings. They are flexible enough to guarantee profitable solutions and structured enough so that we can compute these solutions quickly.