The best-fit heuristic for the rectangular strip packing problem: An efficient implementation and the worst-case approximation ratio

We investigate the best-fit heuristic algorithm by Burke et al. [2004. A new placement heuristic for the orthogonal stock-cutting problem. Operations Research 52, 655–671] for the rectangular strip packing problem. For its simplicity and good performance, the best-fit heuristic has become one of the most significant algorithms for the rectangular strip packing. In this paper, we propose an efficient implementation of the best-fit heuristic that requires O(n)O(n) space and O(nlogn) time, where nn is the number of rectangles. We prove that this complexity is optimal, and we also show the practical usefulness of our implementation via computational experiments. Furthermore, we give the worst-case approximation ratio of the best-fit heuristic.