Approximating the Geometric Knapsack Problem in Near-Linear Time and Dynamically
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913250301444096 |
|---|---|
| author | Buchem, Moritz Deuker, Paul Wiese, Andreas |
| author_facet | Buchem, Moritz Deuker, Paul Wiese, Andreas |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_00536 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Approximating the Geometric Knapsack Problem in Near-Linear Time and Dynamically Buchem, Moritz Deuker, Paul Wiese, Andreas Data Structures and Algorithms 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. |
| title | Approximating the Geometric Knapsack Problem in Near-Linear Time and Dynamically |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2403.00536 |