Linear time-approximation algorithms for bin packing

Simchi-Levi (Naval Res. Logist. 41 (1994) 579-585) proved that the famous bin packing algorithms FF and BF have an absolute worst-case ratio of no more than 7/4, and FFD and BFD have an absolute worst-case ratio of 3/2, respectively. These algorithms run in time O(n log n). In this paper, we provide a linear time constant space (number of bins kept during the execution of the algorithm is constant) off-line approximation algorithms with absolute worst-case ratio 3/2. This result is best possible unless P = NP. Furthermore, we present a linear time constant space on-line algorithm and prove that the absolute worst-case ratio is 7/4. (C) 2000 Elsevier Science B.V. All rights reserved.