The Bottom-Left Algorithm for the Strip Packing Problem

The bottom-left algorithm is a simple heuristic for the Strip Packing Problem. Despite its simplicity, the exact approximation ratio of the bottom-left algorithm remains unknown. We will improve the more-than-40-year-old value for the lower bound from 5/4 to \(4/3 - \varepsilon \) . Additionally, we will show that this lower bound holds even in the special case of squares, where the previously known lower bound was \(12/11 -\varepsilon \) . When squares are arranged in the worst possible order, we establish a constant upper bound and a \(10/3-\varepsilon \) lower bound for the approximation ratio of the BL algorithm. This bound also applies to some online setting and yields an almost tight result there. Finally, we show that the approximation ratio of a local search algorithm based on permuting rectangles in the ordering of the bottom-left algorithm is at least 2 and that such an algorithm may need an exponential number of improvement steps to reach a local optimum.