A 13/6-Approximation for Strip Packing via the Bottom-Left Algorithm
By: Stefan Hougardy, Bart Zondervan
Potential Business Impact:
Packs shapes into a box using less space.
In the Strip Packing problem, we are given a vertical strip of fixed width and unbounded height, along with a set of axis-parallel rectangles. The task is to place all rectangles within the strip, without overlaps, while minimizing the height of the packing. This problem is known to be NP-hard. The Bottom-Left Algorithm is a simple and widely used heuristic for Strip Packing. Given a fixed order of the rectangles, it places them one by one, always choosing the lowest feasible position in the strip and, in case of ties, the leftmost one. Baker, Coffman, and Rivest proved in 1980 that the Bottom-Left Algorithm has approximation ratio 3 if the rectangles are sorted by decreasing width. For the past 45 years, no alternative ordering has been found that improves this bound. We introduce a new rectangle ordering and show that with this ordering the Bottom-Left Algorithm achieves a 13/6 approximation for the Strip Packing problem.
Similar Papers
A 13/6-Approximation for Strip Packing via the Bottom-Left Algorithm
Data Structures and Algorithms
Packs shapes into a tall box better.
Revisiting Chazelle's Implementation of the Bottom-Left Heuristic: A Corrected and Rigorous Analysis
Data Structures and Algorithms
Packs shapes perfectly, saving space and time.
Hierarchical Rectangle Packing Solved by Multi-Level Recursive Logic-based Benders Decomposition
Computational Geometry
Organizes items in boxes, even nested ones.