Approximation Schemes for Geometric Knapsack for Packing Spheres and Fat Objects
<|reference_start|>Approximation Schemes for Geometric Knapsack for Packing Spheres and Fat Objects: 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 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 $\pi/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 not clear 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 which is related to well-studied geometric questions in the realm of circle packing.<|reference_end|>
@article{acharya2024approximation,
    title={Approximation Schemes for Geometric Knapsack for Packing Spheres and Fat
  Objects},
    author={Pritam Acharya, Sujoy Bhore, Aaryan Gupta, Arindam Khan, Bratin
  Mondal, Andreas Wiese},
    journal={arXiv preprint arXiv:2404.03981},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.03981},
    primaryClass={cs.CG}
}