A tight analysis of Brown-Baker-Katseff sequences for online strip packing

Walter Kern, J.J. Paulus

Research output: Contribution to journalArticleAcademicpeer-review

5 Citations (Scopus)

Abstract

We study certain adversary sequences for online strip packing which were first designed and investigated by Brown, Baker and Katseff (Acta Inform. 18:207–225) and determine the optimal competitive ratio for packing such Brown-Baker-Katseff sequences online. As a byproduct of our result, we get a new lower bound of $\rho \geq 3/2 + \sqrt{33}/6 \approx 2.457$ for the competitive ratio of online strip packing.
Original languageUndefined
Pages (from-to)333-344
Number of pages12
JournalJournal of combinatorial optimization
Volume26
Issue number2
DOIs
Publication statusPublished - 2013

Keywords

  • EWI-24506
  • IR-89549
  • METIS-302718
  • Strip Packing
  • On-line algorithm
  • Competitive ratio

Cite this