×

Probabilistic analysis of a heuristic for the dual bin packing problem. (English) Zbl 0682.68045

Summary: We study the probabilistic behavior of the first fit increasing heuristics for the dual bin packing problem. We seek to maximize the number of items that can be packed into m unit capacity bins. We show that when the items to be packed are independent and identically distributed, then the relative error of first fit increasing tends to zero in probability as the number of items tends to infinity. We also consider an on-line variant of this problem and propose a simple heuristics whose relative error tends to zero in probability as the number of items tends to infinity under the assumption that the item sizes are independently and identically distributed according to a distribution with finite mean and with zero in its compact support.

MSC:

68Q25 Analysis of algorithms and problem complexity
65K05 Numerical mathematical programming methods
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bruno, J. L.; Downey, P. J., Probabilistic bounds for dual bin packing, Acta Inform, 22, 333-345 (1985) · Zbl 0569.68037
[2] Chernoff, H., A measure of asymptotic efficiency for tests of a hypothesis based on a sum of observations, Ann. Math. Statist., 23, 493-507 (1952) · Zbl 0048.11804
[3] Coffman, E. G.; Leung, J. Y.; Ting, D. W., Bin packing: Maximizing the number of pieces packed, Acta Inform., 9, 263-271 (1978) · Zbl 0421.68065
[4] Coffman, E. G.; Leung, J. Y., Combinatorial analysis of an efficient algorithm for processor and storage allocation, SIAM J. Comput., 8, 202-217 (1979) · Zbl 0417.68022
[5] Coffman, E. G.; Flatto, L.; Weber, R., Optimal selection of stochastic intervals under a sum constraint, Adv. Appl. Probab., 19, 454-473 (1987) · Zbl 0616.90035
[6] Leung, J. Y., Fast algorithms for packing problems, (Dissertation (1977), Computer Science Dept., Pennsylvania State University: Computer Science Dept., Pennsylvania State University University Park, PA)
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.