2024/03/01 by Buchem, Moritz, Deuker, Paul, Wiese, Andreas · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2403.00536
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.