论文标题
将高管包装成背包的PTA
A PTAS for Packing Hypercubes into a Knapsack
论文作者
论文摘要
我们研究了D维超立方体背包问题，在其中为我们提供了一组具有相关利润的D维超立方体，而Anapsack则是单位D维度超级立方体。目的是找到一个轴对准的超振管子集的非重叠填料，以便最大程度地提高包装的高管的利润。对于这个问题，Harren（ICALP'06）给出了算法，近似值为（1+1/2^d+epsilon）。对于D = 2，Jansen和Solis-OBA（IPCO'08）表明，该问题接受了多项式时间近似方案（PTA）。 Heydrich和Wiese（Soda'17）进一步改善了运行时间，并提供了有效的多项式近似方案（EPTAS）。两种结果都使用2-D填料的结构特性，这些特性并未推广到更高的维度。对于D> 2，获得PTA的开放性仍然开放，实际上，自哈伦的结果以来，没有任何改进。 我们通过提供PTA来解决问题。我们的主要技术贡献是一种结构性引理，表明任何超振的填充物都可以转换为另一个结构化填料，因此，高利润的高纤维子集被封装成恒定数量的特殊型超蛋白，称为V-boxes和n-boxes。作为侧面结果，我们为在更高维度中的带状包装问题的变体提供了几乎最佳的算法。这可能会应用于其他多维几何包装问题。
We study the d-dimensional hypercube knapsack problem 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+epsilon). 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 V-Boxes and N-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.
