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

Walter Kern; J.J. Paulus

doi:10.1007/s10878-012-9463-1

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

Walter Kern, J.J. Paulus

Discrete Mathematics and Mathematical Programming

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

5 Citations (Scopus)

1 Downloads (Pure)

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 language	Undefined
Pages (from-to)	333-344
Number of pages	12
Journal	Journal of combinatorial optimization
Volume	26
Issue number	2
DOIs	https://doi.org/10.1007/s10878-012-9463-1
Publication status	Published - 2013

Keywords

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

Access to Document

10.1007/s10878-012-9463-1

http://eprints.eemcs.utwente.nl/secure2/24506/01/art%253A10.1007%252Fs10878-012-9463-1.pdf

Cite this

@article{2a87f8be60e348ffb4c84d98e4601cc0,

title = "A tight analysis of Brown-Baker-Katseff sequences for online strip packing",

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 \$\textbackslash{}rho \textbackslash{}geq 3/2 + \textbackslash{}sqrt\{33\}/6 \textbackslash{}approx 2.457\$ for the competitive ratio of online strip packing.",

keywords = "EWI-24506, IR-89549, METIS-302718, Strip Packing, On-line algorithm, Competitive ratio",

author = "Walter Kern and J.J. Paulus",

note = "eemcs-eprint-24506 ",

year = "2013",

doi = "10.1007/s10878-012-9463-1",

language = "Undefined",

volume = "26",

pages = "333--344",

journal = "Journal of combinatorial optimization",

issn = "1382-6905",

publisher = "Springer",

number = "2",

}

TY - JOUR

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

AU - Kern, Walter

AU - Paulus, J.J.

N1 - eemcs-eprint-24506

PY - 2013

Y1 - 2013

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

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

KW - EWI-24506

KW - IR-89549

KW - METIS-302718

KW - Strip Packing

KW - On-line algorithm

KW - Competitive ratio

U2 - 10.1007/s10878-012-9463-1

DO - 10.1007/s10878-012-9463-1

M3 - Article

SN - 1382-6905

VL - 26

SP - 333

EP - 344

JO - Journal of combinatorial optimization

JF - Journal of combinatorial optimization

IS - 2

ER -