A note on the lower bound for online strip packing

Walter Kern, J.J. Paulus

Research output: Book/ReportReportProfessional

36 Downloads (Pure)

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.
Original languageUndefined
Place of PublicationEnschede
PublisherUniversity of Twente
Number of pages9
Publication statusPublished - Feb 2009

Publication series

Name
PublisherDepartment of Applied Mathematics, University of Twente
No.1893
ISSN (Print)1874-4850
ISSN (Electronic)1874-4850

Keywords

  • EWI-15127
  • METIS-263747
  • IR-65403

Cite this

Kern, W., & Paulus, J. J. (2009). A note on the lower bound for online strip packing. Enschede: University of Twente.