Answers are grounded in this paper and cite their sources.
The bottom-left algorithm is a simple heuristic for the Strip Packing Problem. It places the rectangles in the given order at the lowest free position in the strip, using the left most position in case of ties. 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 - ε. 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 -ε. These lower bounds apply regardless of the ordering of the rectangles. When squares are arranged in the worst possible order, we establish a constant upper bound and a 10/3-ε lower bound for the approximation ratio of the bottom-left 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.
No takes yet. Share an insight, caveat, or question.
Hougardy et al. (2024) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: