Approximation Schemes for Geometric Knapsack for Packing Spheres and Fat Objects

Abstract

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 + ε)-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 ≥ 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 PTAS for disks and hyperspheres, we output the computed set of objects, but for a Oε(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 + ε)-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. © Pritam Acharya, Sujoy Bhore, Aaryan Gupta, Arindam Khan, Bratin Mondal, and Andreas Wiese.