Balogh, János; Békési, József; Galambos, Gábor; Dósa, György; Tan, Zhiyi Lower bound for 3-batched bin packing. (English) Zbl 1387.90205 Discrete Optim. 21, 14-24 (2016). Summary: In this paper we will consider a special relaxation of the well-known online bin packing problem. In a batched bin packing problem (BBPP)-defined by G. Gutin et al. [Discrete Optim. 2, No. 1, 71–82 (2005; Zbl 1140.90476)] – the elements come in batches and one batch is available for packing in a given time. If we have \(K\geq 2\) batches then we denote the problem by \(K\)-BBPP. In [loc. cit.] the authors gave a \(1.3871\dots\) lower bound for the asymptotic competitive ratio (ACR) of any on-line \(2\)-BBBP algorithm. In this paper we investigate the 3-BBPP, and we give \(1.51211\dots\) lower bound for its ACR. Cited in 12 Documents MSC: 90C27 Combinatorial optimization 90C60 Abstract computational complexity for mathematical programming problems Keywords:batched bin packing; worst-case behavior; lower bound Citations:Zbl 1140.90476 PDFBibTeX XMLCite \textit{J. Balogh} et al., Discrete Optim. 21, 14--24 (2016; Zbl 1387.90205) Full Text: DOI References: [2] Balogh, J.; Békési, J.; Galambos, G., New lower bounds for certain classes of bin packing algorithms, Theoret. Comput. Sci., 440-441, 1-13 (2012) · Zbl 1247.68339 [3] Johnson, D. S., Near-optimal bin-packing algorithms (1973), MIT: MIT Cambridge, (Doctoral Thesis) [4] Lee, C. C.; Lee, D. T., A simple on-line packing algorithm, J. ACM, 32, 562-572 (1985) · Zbl 0629.68045 [6] Coffman, E.; Csirik, J.; Galambos, G.; Martello, S.; De Vigo, D., Bin packing approximation algorithms: Survey and classification, (Du, D.-Z.; Pardalos, P. M.; Graham, R. L., Handbook of Combinatorial Optimization (2013), Springer: Springer New York), 455-531 [7] Gutin, G.; Jensen, T.; Yeo, A., Batched bin packing, Discrete Optim., 2, 1, 71-82 (2005) · Zbl 1140.90476 [8] Dósa, Gy., Batched bin packing revisited, J. Sched. (2015), in press · Zbl 1373.90054 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.