A note on online strip packing

Deshi Ye (), Xin Han () and Guochuan Zhang ()
Additional contact information
Deshi Ye: Zhejiang University
Xin Han: University of Hong Kong
Guochuan Zhang: Zhejiang University

Journal of Combinatorial Optimization, 2009, vol. 17, issue 4, No 5, 417-423

Abstract: 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 $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.

Keywords: Strip packing; Online algorithms; Competitive ratio (search for similar items in EconPapers)
Date: 2009
References: View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-007-9125-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:17:y:2009:i:4:d:10.1007_s10878-007-9125-x

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-007-9125-x

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().