Tight bounds for NF-based bounded-space online bin packing algorithms |
| |
Authors: | József Békési Gábor Galambos |
| |
Affiliation: | 1.Department of Applied Informatics, Gyula Juhász Faculty of Education,University of Szeged,Szeged,Hungary |
| |
Abstract: | 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.44ldots ) for any given buffer size not less than 1. They also gave a lower bound of (4/3=1.33ldots ) 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_infty (r)) for the r-parametric problem when the buffer capacity is 3. Since (h_infty (2) = 1.42312ldots ), 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|