A note on online strip packing |
| |
| Authors: | Deshi Ye Xin Han Guochuan Zhang |
| |
| Institution: | (1) College of Computer Science, Zhejiang University, Hangzhou, 310027, China;(2) Department of Computer Science, University of Hong Kong, Hong Kong, Hong Kong;(3) Department of Mathematics, Zhejiang University, Hangzhou, 310027, China |
| |
| Abstract: | 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
is First 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 of
without the restriction on rectangle heights. Our algorithm also beats the best known online algorithm for parallel job scheduling.
Ye’s research supported by NSFC(10601048).
Zhang’s research supported by NSFC(60573020). |
| |
| Keywords: | Strip packing Online algorithms Competitive ratio |
| 本文献已被 SpringerLink 等数据库收录！ |
|
