Approximation Schemes for Geometric Knapsack for Packing Spheres and Fat Objects
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912166882312192 |
|---|---|
| author | Acharya, Pritam Bhore, Sujoy Gupta, Aaryan Khan, Arindam Mondal, Bratin Wiese, Andreas |
| author_facet | Acharya, Pritam Bhore, Sujoy Gupta, Aaryan Khan, Arindam Mondal, Bratin Wiese, Andreas |
| contents | We study the geometric knapsack problem in which we are given a set of $d$-dimensional objects (each with associated profits) and the goal is to find the maximum profit subset that can be packed non-overlappingly into a given $d$-dimensional (unit hypercube) knapsack. Even if $d=2$ and all input objects are disks, this problem is known to be \textsf{NP}-hard [Demaine, Fekete, Lang, 2010]. In this paper, we give polynomial time $(1+\varepsilon)$-approximation algorithms for the following types of input objects in any constant dimension $d$:
- disks and hyperspheres,
- a class of fat convex polygons that generalizes regular $k$-gons for $k\ge 5$ (formally, polygons
with a constant number of edges, whose lengths are in a bounded range, and in which each angle is strictly larger than $π/2$),
- arbitrary fat convex objects that are sufficiently small compared to the knapsack.
We remark that in our \textsf{PTAS} for disks and hyperspheres, we output the computed set of objects, but for a $O_\varepsilon(1)$ of them, we determine their coordinates only up to an exponentially small error. However, it is unclear whether there always exists a $(1+\varepsilon)$-approximate solution that uses only rational coordinates for the disks' centers. We leave this as an open problem that is related to well-studied geometric questions in the realm of circle packing. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_03981 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Approximation Schemes for Geometric Knapsack for Packing Spheres and Fat Objects Acharya, Pritam Bhore, Sujoy Gupta, Aaryan Khan, Arindam Mondal, Bratin Wiese, Andreas Computational Geometry We study the geometric knapsack problem in which we are given a set of $d$-dimensional objects (each with associated profits) and the goal is to find the maximum profit subset that can be packed non-overlappingly into a given $d$-dimensional (unit hypercube) knapsack. Even if $d=2$ and all input objects are disks, this problem is known to be \textsf{NP}-hard [Demaine, Fekete, Lang, 2010]. In this paper, we give polynomial time $(1+\varepsilon)$-approximation algorithms for the following types of input objects in any constant dimension $d$: - disks and hyperspheres, - a class of fat convex polygons that generalizes regular $k$-gons for $k\ge 5$ (formally, polygons with a constant number of edges, whose lengths are in a bounded range, and in which each angle is strictly larger than $π/2$), - arbitrary fat convex objects that are sufficiently small compared to the knapsack. We remark that in our \textsf{PTAS} for disks and hyperspheres, we output the computed set of objects, but for a $O_\varepsilon(1)$ of them, we determine their coordinates only up to an exponentially small error. However, it is unclear whether there always exists a $(1+\varepsilon)$-approximate solution that uses only rational coordinates for the disks' centers. We leave this as an open problem that is related to well-studied geometric questions in the realm of circle packing. |
| title | Approximation Schemes for Geometric Knapsack for Packing Spheres and Fat Objects |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2404.03981 |