A tight Analysis of Brown-Baker-Katseff Sequences for Online Strip Packing.
Walter Kern, Jacob Jan Paulus · Cologne Twente Workshop on Graphs and Combinatorial Optimization · 2010
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 \ge 3/2+\sqrt{33}/6 \approx 2.457$ for the competitive ratio of online strip packing.