Improved Lower Bound for Online Strip Packing
Improved Lower Bound for Online Strip Packing
复制标题
DOI：
10.1007/s00224-013-9494-8
复制
发表时间：
2013
影响因子：
0.5
通讯作者：
Rolf Harren;W. Kern
中科院分区：
文献类型：
--
作者：
Rolf Harren;W. Kern
研究了在线带装箱问题，得到了该问题竞争比的改进下界ρ≥2.589.该构建基于修改的“Brown-Baker-Katseff序列”（Brown等人，Acta Inform. 18：207-225，1982），仅使用两种类型的矩形。此外，我们提出了一个在线算法与竞争ratiofpacking这种类型的实例。
We study the online strip packing problem and derive an improved lower bound ofρ≥2.589… for the competitive ratio of this problem. The construction is based on modified “Brown-Baker-Katseff sequences” (Brown et al. in Acta Inform. 18:207–225, 1982) using only two types of rectangles. In addition, we present an online algorithm with competitive ratiofor packing instances of this type.