Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms

TLDR

The bin‑packing problem, where items of size between 0 and l must be placed into the fewest bins without exceeding capacity, is a classic NP‑hard problem with many practical applications. This study investigates how well simple heuristics—first‑fit and best‑fit—perform relative to the optimal solution. First‑fit places each item into the first bin that fits, while best‑fit places it into the most nearly full bin that fits. Both algorithms use at most 1.7 L* + 2 bins, and when items are sorted decreasingly at most 1.22 L* + 4 bins, with these bounds shown to be essentially tight and also holding for lists with all items ≤ α < 1.

Abstract

The following abstract problem models several practical problems in computer science and operations research: given a list L of real numbers between 0 and l, place the elements of L into a minimum number $L^ * $ of “bins” so that no bin contains numbers whose sum exceeds l. Motivated by the likelihood that an excessive amount of computation will be required by any algorithm which actually determines an optimal placement, we examine the performance of a number of simple algorithms which obtain “good” placements. The first-fit algorithm places each number, in succession, into the first bin in which it fits. The best-fit algorithm places each number, in succession, into the most nearly full bin in which it fits. We show that neither the first-fit nor the best-fit algorithm will ever use more than $\frac{17}{10}L^ * + 2$ bins. Furthermore, we outline a proof that, if L is in decreasing order, then neither algorithm will use more than $\frac{11}{9} L^ * + 4$ bins. Examples are given to show that both upper bounds are essentially the best possible. Similar results are obtained when the list L contains no numbers larger than $\alpha < 1$.