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 |
| LEADER | 02248nab a2200241 i 4500 | ||
|---|---|---|---|
| 001 | publ28445 | ||
| 005 | 20231017142113.0 | ||
| 008 | 231017s2018 hu o 0|| Angol d | ||
| 022 | |a 1382-6905 | ||
| 024 | 7 | |a 10.1007/s10878-017-0175-4 |2 doi | |
| 024 | 7 | |a 3272000 |2 mtmt | |
| 040 | |a SZTE Publicatio Repozitórium |b hun | ||
| 041 | |a Angol | ||
| 100 | 1 | |a Békési József | |
| 245 | 1 | 0 | |a Tight bounds for NF-based bounded-space online bin packing algorithms |h [elektronikus dokumentum] / |c Békési József |
| 260 | |c 2018 | ||
| 300 | |a 350-364 | ||
| 490 | 0 | |a JOURNAL OF COMBINATORIAL OPTIMIZATION |v 35 No. 2 | |
| 520 | 3 | |a 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. | |
| 650 | 4 | |a Számítás- és információtudomány | |
| 700 | 0 | 1 | |a Galambos Gábor |e aut |
| 856 | 4 | 0 | |u http://publicatio.bibl.u-szeged.hu/28445/1/nfbased0723.pdf |z Dokumentum-elérés |
| 856 | 4 | 0 | |u http://publicatio.bibl.u-szeged.hu/28445/3/3272000_megjelent.pdf |z Dokumentum-elérés |