Improved Lower Bound for Online Strip Packing

Rolf Harren, Walter Kern

Research output: Contribution to journalArticleAcademicpeer-review

6 Citations (Scopus)
14 Downloads (Pure)

Abstract

We study the online strip packing problem and derive an improved lower bound of Ͽ ≥ 2.589... 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 (3 + √5)/2 = 2.618... for packing instances of this type.
Original languageUndefined
Pages (from-to)41-72
Number of pages32
JournalTheoretical computer science
Volume56
Issue number1
DOIs
Publication statusPublished - Jan 2015

Keywords

  • EWI-26407
  • Lower bounds
  • Rectangle packing
  • IR-98339
  • On-line algorithms
  • METIS-314997
  • Strip Packing

Cite this