Linear-time-approximation algorithms for bin packing

Simchi–Levi 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 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.