A New Asymptotic Approximation Algorithm for 3-Dimensional Strip Packing
A New Asymptotic Approximation Algorithm for 3-Dimensional Strip Packing
复制标题
DOI：
10.1007/978-3-319-04298-5_29
复制
发表时间：
2014-01
期刊：
影响因子：
--
通讯作者：
K. Jansen;Lars Prädel
中科院分区：
文献类型：
--
作者：
K. Jansen;Lars Prädel
我们研究 3 维条带包装问题：给定一个 nboxesb1,…,bn 列表，其宽度 wi≤ 1，深度di≤ 1 和任意长度 ℓi。目标是将所有盒子打包成宽度和深度为1且长度无限的条带，从而使打包长度最小化。这些框不得重叠或旋转。我们提出了 Bansal 等人对当前最佳渐近逼近比 1.692 的改进。[2]对于任何 ε> 0 具有渐近 3/2 +ε 近似。
We study the 3-dimensional Strip Packing problem: Given a list ofnboxesb1,…,bnof the widthwi≤ 1, depthdi≤ 1 and an arbitrary length ℓi. The objective is to pack all boxes into a strip of the width and depth 1 and infinite length, so that the packing length is minimized. The boxes may not overlap or be rotated. We present an improvement of the current best asymptotic approximation ratio of 1.692 by Bansal et al.[2] with an asymptotic 3/2 +ε-approximation for anyε> 0.