English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Journal Article

Improved Lower Bound for Online Strip Packing

MPS-Authors
/persons/resource/persons44587

Harren,  Rolf
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

Harren, R., & Kern, W. (2015). Improved Lower Bound for Online Strip Packing. Theory of Computing Systems, 56(1), 41-72. doi:10.1007/s00224-013-9494-8.


Cite as: http://hdl.handle.net/11858/00-001M-0000-0024-E518-4
Abstract
We study the online strip packing problem and derive an improved lower bound of rho a parts per thousand yen2.589aEuro broken vertical bar for the competitive ratio of this problem. The construction is based on modified "Brown-Baker-Katseff sequences" (Brown et al. in Acta Inform. 18:207-225, 1982) using only two types of rectangles. In addition, we present an online algorithm with competitive ratio for packing instances of this type.