A 4-Space Bounded Approximation Algorithm for Online Bin Packing Problem

In this work, we study the well-known online bin packing problem and propose a new approximation algorithm under the restriction of linear time and constant bounded space. In this setting, Lee and Lee in 1985 [12] introduced an algorithm called Harmonic that achieves the asymptotic approximation ratio (AAR) of T_∞≈ 1.69, and showed that no O(1)-space algorithm can obtain competitive ratio better than T_∞. Zhang et al. in 2000 [15] presented a linear time constant bounded space (number of bins kept during the execution of the algorithm is constant) online algorithm and proved that the absolute worst-case ratio is 74=1.75. We extend Zhang et al. ’s work to consider three types of bins, and show that our proposed algorithm uses no more than ⌈5532·OPT⌉ bins. We first prove that the asymptotic approximation ratio is at most 5532=1.71875 by using the weight function, then we show that the additive term could be reduced from 3 to less than 1 if post-processing repacking is allowed. In the end, we provide a worst-case analysis and prove that the upper bound of 5532 is tight.