A note on online strip packing

• DOI: 10.1007/s10878-007-9125-x
• Publication Date: 2008-01-04T15:26:53Z
• Authors: Deshi Ye; Xin Han; Guochuan Zhang
• Keywords: 0102 computer and information sciences; 01 natural sciences

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 \(7/2+\sqrt{10}\approx 6.6623\) without the restriction on rectangle heights. Our algorithm also beats the best known online algorithm for parallel job scheduling.