Linear time-approximation algorithms for bin packing (Q1591548): Difference between revisions

\textit{D. Simchi-Levi} [Naval Res. Logist. 41, 579-585 (1994; Zbl 0809.90111)] proved the famous bin packing algorithms FF and BF have an absolute worst-case ratio of no more than \({7\over 4}\), and FFD and BFD have an absolute worst-case ratio of \({3\over 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\over 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\over 4}\).