Improved Lower Bound for Online Strip Packing
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:207225, 1982) using only two types of rectangles. In addition, we present an online algorithm with competitive ratio \((3+\sqrt{5})/2 = 2.618\ldots\) for packing instances of this type.
lower bounds strip packing online algorithms rectangle packing