2026-07-22T19:33:49Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16419 2024-03-06T10:57:26Z ddc:004 open_access

A PTAS for Packing Hypercubes into a Knapsack Jansen, Klaus Khan, Arindam Lira, Marvin Sreenivas, K. V. N. Multidimensional knapsack geometric packing cube packing strip packing We study the d-dimensional hypercube knapsack problem ({d}-D Hc-Knapsack) where we are given a set of d-dimensional hypercubes with associated profits, and a knapsack which is a unit d-dimensional hypercube. The goal is to find an axis-aligned non-overlapping packing of a subset of hypercubes such that the profit of the packed hypercubes is maximized. For this problem, Harren (ICALP'06) gave an algorithm with an approximation ratio of (1+1/2^d+ε). For d = 2, Jansen and Solis-Oba (IPCO'08) showed that the problem admits a polynomial-time approximation scheme (PTAS); Heydrich and Wiese (SODA'17) further improved the running time and gave an efficient polynomial-time approximation scheme (EPTAS). Both the results use structural properties of 2-D packing, which do not generalize to higher dimensions. For d > 2, it remains open to obtain a PTAS, and in fact, there has been no improvement since Harren’s result. We settle the problem by providing a PTAS. Our main technical contribution is a structural lemma which shows that any packing of hypercubes can be converted into another structured packing such that a high profitable subset of hypercubes is packed into a constant number of special hypercuboids, called 𝒱-Boxes and 𝒩-Boxes. As a side result, we give an almost optimal algorithm for a variant of the strip packing problem in higher dimensions. This might have applications for other multidimensional geometric packing problems. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Klaus Jansen and Arindam Khan and Marvin Lira and K. V. N. Sreenivas 2022 Is Part Of LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2022.78 urn:nbn:de:0030-drops-164192 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.78 eng https://creativecommons.org/licenses/by/4.0/legalcode