2026-07-26T10:48:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12491 2024-03-06T10:50:16Z ddc:004 open_access

On the Two-Dimensional Knapsack Problem for Convex Polygons Merino, Arturo Wiese, Andreas Approximation algorithms geometric knapsack problem polygons rotation 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 to rotate the polygons by arbitrary angles. We present a quasi-polynomial time O(1)-approximation algorithm for the general case and a polynomial time O(1)-approximation algorithm if all input polygons are triangles, both assuming polynomially bounded integral input data. Also, we give a quasi-polynomial time algorithm that computes a solution of optimal weight under 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. 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Arturo Merino and Andreas Wiese 2020 Is Part Of LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2020.84 urn:nbn:de:0030-drops-124916 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.84 eng https://creativecommons.org/licenses/by/3.0/legalcode