Bart Zondervan

dblp:371/4222 · DBLP profile ↗
← Back
2ranked-venue papers
0as first author
2since 2021 · last 2026
0009-0003-6814-3024ORCID · corroborated

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 2 · 2 since 2021
YearPublicationVenuePosition
2026 A 13/6-Approximation for Strip Packing via the Bottom-Left Algorithm
abstract
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.
Stefan Hougardy, Bart Zondervan
STACS2
2024 The Bottom-Left Algorithm for the Strip Packing Problem
Stefan Hougardy, Bart Zondervan
IWOCA2