Tight bounds for NF-based bounded-space online bin packing algorithms

József Békési () and Gábor Galambos ()
Additional contact information
József Békési: University of Szeged
Gábor Galambos: University of Szeged

Journal of Combinatorial Optimization, 2018, vol. 35, issue 2, No 3, 350-364

Abstract: 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.44\ldots $$ 13 / 9 = 1.44 … for any given buffer size not less than 1. They also gave a lower bound of $$4/3=1.33\ldots $$ 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_\infty (r)$$ h ∞ ( r ) for the r-parametric problem when the buffer capacity is 3. Since $$h_\infty (2) = 1.42312\ldots $$ 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.

Keywords: Semi-online bin-packing; Bounded-space; Asymptotic competitive ratio; Next-fit; Lower bound (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-017-0175-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:35:y:2018:i:2:d:10.1007_s10878-017-0175-4

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-017-0175-4

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().