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

Walter Kern, J.J. Paulus

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 language Undefined 333-344 12 Journal of combinatorial optimization 26 2 https://doi.org/10.1007/s10878-012-9463-1 Published - 2013

## Keywords

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