A note on online strip packing
A note on online strip packing
复制标题
在线带状包装注意事项
DOI：
10.1007/s10878-007-9125-x
复制
发表时间：
2009-05
影响因子：
1
通讯作者：
Ye, Deshi
中科院分区：
文献类型：
--
作者：
Zhang, Guochuan;Han, Xin;Ye, Deshi
在在线条形包装中，我们被要求将一系列矩形逐个包装成一个单位宽度的垂直条形，而不需要任何关于未来矩形的信息。目标是最小化所用条带的总高度。最著名的算法是First Fit Shelf算法（Baker和施瓦茨在SIAM J. Comput. 12（3）：508-525，1983），其在假设每个矩形的高度从上方以1为界的情况下具有6.99的绝对竞争比。我们改进了货架算法，在不限制矩形高度的情况下，给出了绝对竞争比。我们的算法也击败了最有名的在线并行作业调度算法。
In online strip packing we are asked to pack a list of rectangles one by one into a vertical strip of unit width, without any information about future rectangles. The goal is to minimize the total height of strip used. The best known algorithm isFirst Fit Shelf algorithm(Baker and Schwarz in SIAM J. Comput. 12(3):508–525, 1983), which has an absolute competitive ratio of 6.99 under the assumption that the height of each rectangle is bounded from above by one. We improve the shelf algorithm and show an absolute competitive ratio ofwithout the restriction on rectangle heights. Our algorithm also beats the best known online algorithm for parallel job scheduling.
登录
查看更多内容
在线调度列表中的并行作业
影响因子：
2
作者：
Zhang, Guochuan;Ye, Deshi
通讯作者：
Ye, Deshi
DOI：
10.1007/978-3-540-77918-6_6
发表时间：
2007-10
期刊：
--
影响因子：
--
作者：
J. Hurink;J. J. Paulus-J.
通讯作者：
J. Hurink;J. J. Paulus-J.
DOI：
10.1007/bfb0029561
发表时间：
1998
期刊：
Lecture Notes in Computer Science
影响因子：
--
作者：
A. Fiat;G. Woeginger
通讯作者：
A. Fiat;G. Woeginger
DOI：
--
发表时间：
1998
期刊：
Lecture Notes in Computer Science
影响因子：
--
作者：
J. Csirik;Gj Gerhard Woeginger
通讯作者：
J. Csirik;Gj Gerhard Woeginger
DOI：
10.1145/1060590.1060702
发表时间：
2005-05
期刊：
--
影响因子：
--
作者：
K. Jansen;R. V. Stee
通讯作者：
K. Jansen;R. V. Stee