×

Lower bound for 3-batched bin packing. (English) Zbl 1387.90205

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.

MSC:

90C27 Combinatorial optimization
90C60 Abstract computational complexity for mathematical programming problems

Citations:

Zbl 1140.90476
PDFBibTeX XMLCite
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.