Improved Lower Bound for Online Strip Packing

Rolf Harren; Walter Kern

doi:10.1007/s00224-013-9494-8

Improved Lower Bound for Online Strip Packing

Rolf Harren, Walter Kern

Discrete Mathematics and Mathematical Programming

Research output: Contribution to journal › Article › Academic › peer-review

7 Citations (Scopus)

44 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 language	English
Pages (from-to)	41-72
Number of pages	32
Journal	Theoretical computer science
Volume	56
Issue number	1
DOIs	https://doi.org/10.1007/s00224-013-9494-8
Publication status	Published - Jan 2015

Keywords

EWI-26407
Lower bounds
Rectangle packing
IR-98339
On-line algorithms
METIS-314997
Strip Packing
n/a OA procedure

Access to Document

10.1007/s00224-013-9494-8

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, n/a OA procedure",

author = "Rolf Harren and Walter Kern",

note = "eemcs-eprint-26407 ",

year = "2015",

month = jan,

doi = "10.1007/s00224-013-9494-8",

language = "English",

volume = "56",

pages = "41--72",

journal = "Theoretical computer science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "1",

}

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

KW - n/a OA procedure

U2 - 10.1007/s00224-013-9494-8

DO - 10.1007/s00224-013-9494-8

M3 - Article

SN - 0304-3975

VL - 56

SP - 41

EP - 72

JO - Theoretical computer science

JF - Theoretical computer science

IS - 1

ER -

Improved Lower Bound for Online Strip Packing

Abstract

Keywords

Access to Document

Fingerprint

Cite this