Tight bounds for NF-based bounded-space online bin packing algorithms
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 l...
Elmentve itt :
| Szerzők: | |
|---|---|
| Dokumentumtípus: | Cikk |
| Megjelent: |
2018
|
| Sorozat: | JOURNAL OF COMBINATORIAL OPTIMIZATION
35 No. 2 |
| Tárgyszavak: | |
| doi: | 10.1007/s10878-017-0175-4 |
| mtmt: | 3272000 |
| Online Access: | http://publicatio.bibl.u-szeged.hu/28445 |
| Tartalmi kivonat: | 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. |
|---|---|
| Terjedelem/Fizikai jellemzők: | 350-364 |
| ISSN: | 1382-6905 |