Approximation Algorithms for Multiple Strip Packing
Approximation Algorithms for Multiple Strip Packing
复制标题
DOI：
10.1007/978-3-642-12450-1_4
复制
发表时间：
2009-09
期刊：
影响因子：
--
通讯作者：
Marin Bougeret;P. Dutot;Klaus Jansen;Christina Robenek;D. Trystram
中科院分区：
文献类型：
--
作者：
Marin Bougeret;P. Dutot;Klaus Jansen;Christina Robenek;D. Trystram
在本文中，我们研究了多条包装（MSP）问题，著名的带包装问题的推广。对于给定的矩形集合r1，...，rn，高度和宽度≤ 1，目标是找到一个不重叠的正交填充，不旋转到k ∈ [0，1]×[0，∞），最小化高度的最大值。我们提出了一个近似算法的绝对比为2，这是最好的可能，除非，和以前的最佳结果的比2 +ε的改进。此外，我们提出了简单的基于货架的算法与短的运行时间和AFPTAS的MSP。由于MSP是强困难的，FPTAS被排除，AFPTAS也是近似理论意义下的最佳可能结果。
In this paper we study the Multiple Strip Packing (MSP) problem, a generalization of the well-known Strip Packing problem. For a given set of rectangles,r1,...,rn, with heights and widths ≤ 1, the goal is to find a non-overlapping orthogonal packing without rotations intok∈ ℕ strips [0,1]×[0, ∞ ), minimizing the maximum of the heights. We present an approximation algorithm with absolute ratio 2, which is the best possible, unless, and an improvement of the previous best result with ratio 2 +ε. Furthermore we present simple shelf-based algorithms with short running-time and an AFPTAS for MSP. Since MSP is strongly-hard, an FPTAS is ruled out and an AFPTAS is also the best possible result in the sense of approximation theory.