A note on the lower bound for online strip packing

Share/Save/Bookmark

Kern, W. and Paulus, J.J. (2009) A note on the lower bound for online strip packing. [Report]

open access
[img]
Preview
PDF
117kB
Abstract:This note presents a lower bound of $3/2+\sqrt{33}/6 \approx 2.457$ on the competitive ratio for online strip packing. The instance construction we use to obtain the lower bound was first coined by Brown, Baker and Katseff (1980). Recently this instance construction is used to improve the lower bound in computer aided proofs. We derive the best possible lower bound that can be obtained with this instance construction.
Item Type:Report
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/65403
Official URL:http://www.math.utwente.nl/publications/
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page