Improved Lower Bound for Online Strip Packing

Rolf Harren, Walter Kern

Research output: Contribution to journalArticleAcademicpeer-review

5 Citations (Scopus)
10 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

@article{3051d9acd66845c78b12f8bd88fb9822,
title = "Improved Lower Bound for Online Strip Packing",
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.",
keywords = "EWI-26407, Lower bounds, Rectangle packing, IR-98339, On-line algorithms, METIS-314997, Strip Packing",
author = "Rolf Harren and Walter Kern",
note = "eemcs-eprint-26407",
year = "2015",
month = "1",
doi = "10.1007/s00224-013-9494-8",
language = "Undefined",
volume = "56",
pages = "41--72",
journal = "Theoretical computer science",
issn = "0304-3975",
publisher = "Elsevier",
number = "1",

}

Improved Lower Bound for Online Strip Packing. / Harren, Rolf; Kern, Walter.

In: Theoretical computer science, Vol. 56, No. 1, 01.2015, p. 41-72.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Improved Lower Bound for Online Strip Packing

AU - Harren, Rolf

AU - Kern, Walter

N1 - eemcs-eprint-26407

PY - 2015/1

Y1 - 2015/1

N2 - 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.

AB - 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.

KW - EWI-26407

KW - Lower bounds

KW - Rectangle packing

KW - IR-98339

KW - On-line algorithms

KW - METIS-314997

KW - Strip Packing

U2 - 10.1007/s00224-013-9494-8

DO - 10.1007/s00224-013-9494-8

M3 - Article

VL - 56

SP - 41

EP - 72

JO - Theoretical computer science

JF - Theoretical computer science

SN - 0304-3975

IS - 1

ER -