On the two-dimensional knapsack problem for convex polygons.

Abstract: We study the two-dimensional geometric knapsack problem for convex polygons. Given a set of weighted convex polygons and a square knapsack, the goal is to select the most profitable subset of the given polygons that fits non-overlappingly into the knapsack. We allow rotating the polygons by arbitrary angles.

In this talk we will first present:

– a quasi-poly time O(1)-approximation

– a poly time O(1)-approximation algorithm if all input polygons are triangles.

We will then look into the setting of resource augmentation, i.e., we allow to increase the size of the knapsack by a factor of 1 + δ for some δ > 0 but compare ourselves with the optimal solution for the original knapsack. In the resource augmentation setting we present:

– a poly time O(1)-approximation

– a quasi-poly time algorithm that computes a solution of optimal weight.

To the best of our knowledge, these are the first results for two-dimensional geometric knapsack in which the input objects are more general than axis-parallel rectangles or circles and in which the input polygons can be rotated by arbitrary angles.

This is joint work with Andreas Wiese.

Posted on Oct 26, 2020 in ACGO, Seminars