Tight bounds for NF-based bounded-space online bin packing algorithms - Békési József (JOURNAL OF COMBINATORIAL OPTIMIZATION, 2018)
In Zheng et al. (J Comb Optim 30(2):360–369, 2015) modelled a surgery problem by the one-dimensional bin packing, and developed a semi-online algorithm to give an efficient feasible solution. In their algorithm they used a buffer to temporarily store items, having a possibility to lookahead in the list. Because of the considered practical problem they investigated the 2-parametric case, when the size of the items is at most 1/2. Using an NF-based online algorithm the authors proved an ACR of 13/9 = 1.44 … for any given buffer size not less than 1. They also gave a lower bound of 4/3 = 1.33 … for the bounded-space algorithms that use NF-based rules. Later, in Zhang et al. (J Comb Optim 33(2):530–542, 2017) an algorithm was given with an ACR of 1.4243, and the authors improved the lower bound to 1.4230. In this paper we present a tight lower bound of h∞ (r) for the r-parametric problem when the buffer capacity is 3. Since h∞ (2) = 1.42312 …, our result—as a special case—gives a tight bound for the algorithm-class given in 2017. To prove that the lower bound is tight, we present an NF-based online algorithm that considers the r-parametric problem, and uses a buffer with capacity of 3. We prove that this algorithm has an ACR that is equal to the lower bounds for arbitrary r. © Springer Science+Business Media, LLC 2017.