New upper bounds for online strip packing
New upper bounds for online strip packing
复制标题
在线带状包装的新上限
DOI：
10.1016/j.disopt.2016.11.004
复制
发表时间：
2017-02
影响因子：
1.1
通讯作者：
Jiaoliao Xiao
中科院分区：
文献类型：
--
作者：
Guosong Yu;Yanling Mao;Jiaoliao Xiao
In this paper, we consider the online strip packing problem, in which a list of online rectangles has to be packed without overlap or rotation into one or more strips of width 1 and infinite height so as to minimize the required height of the packing. By analyzing a two-phase shelf algorithm, we derive a new upper bound 6.4786 on the competitive ratio for online one strip packing. This result improves the best known upper bound of 6.6623. We also extend this algorithm to online multiple strips packing and present some numeric upper bounds on their competitive ratios which are better than the previous bounds.
登录
查看更多内容
DOI：
10.1007/978-3-540-77918-6_6
发表时间：
2007-10
期刊：
--
影响因子：
--
作者：
J. Hurink;J. J. Paulus-J.
通讯作者：
J. Hurink;J. J. Paulus-J.
影响因子：
1
作者：
W. Kern;J. J. Paulus-J.
通讯作者：
W. Kern;J. J. Paulus-J.
在线带状包装注意事项
影响因子：
1
作者：
Zhang, Guochuan;Han, Xin;Ye, Deshi
通讯作者：
Ye, Deshi
DOI：
--
发表时间：
2021
期刊：
--
影响因子：
--
作者：
Institut f¨ur Mathematik;B. Johannes
通讯作者：
Institut f¨ur Mathematik;B. Johannes
DOI：
10.1137/0209062
发表时间：
1980-11
期刊：
SIAM J. Comput.
影响因子：
--
作者：
E. Coffman;M. Garey;David S. Johnson;R. Tarjan
通讯作者：
E. Coffman;M. Garey;David S. Johnson;R. Tarjan