×

Dual bin packing with items of random sizes. (English) Zbl 0780.90074

Summary: Given a collection of items and a number of unit size bins, the dual bin packing problem requires finding the largest number of items that can be packed in these bins. In our stochastic model, the item sizes \(X_ 1,\dots,X_ n\) are independent identically distributed according to a given probability measure \(\mu\). Denote by \(N_ n=N_ n(X_ 1,\dots,X_ n)\) the largest number of these items that can be packed in \(\lfloor an\rfloor\) bins, where \(0<a<1\) is a constant. We show that \(b=\lim_{n\to\infty} E(N_ n)/n\) exists, and that the random variable \((N_ n-nb)/\sqrt n\) converges in distribution. The limit is identified as the distribution of the supremum of a certain Gaussian process canonically attached to \(\mu\).

MSC:

90C15 Stochastic programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] L. Breiman,Probability (Addison-Wesley, Reading, MA, 1968).
[2] J.L. Bruno and P.J. Downey, ”Probabilistic bounds for dual bin packing,”Acta Informatica 22 (1985) 333–345. · Zbl 0569.68037
[3] E.G. Coffman Jr., J.Y. Leung and D.W. Ting, ”Bin packing, maximizing the number of pieces packed,”Acta Informatica 9 (1978) 263–271. · Zbl 0421.68065 · doi:10.1007/BF00288885
[4] R. Engelking,General Topology (PWN, Warsaw, 1977).
[5] D. Foster and R. Vohra, ”Probabilistic analysis of a heuristic for the dual bin packing problem,”Information Processing Letters 31 (1989) 287–290. · Zbl 0682.68045 · doi:10.1016/0020-0190(89)90088-4
[6] J. Komlós, P. Major and G. Tuesnády, ”An approximation of partial sums of independent random variables and the sample DFI,”Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete 32 (1975) 111–131. · Zbl 0308.60029 · doi:10.1007/BF00533093
[7] W. Rhee and M. Talagrand, ”Martingale inequality and NP-complete problems,”Mathematics of Operation Research 12(1) (1987) 177–181. · Zbl 0718.60040 · doi:10.1287/moor.12.1.177
[8] W. Rhee, ”Optimal bin packing with items of random sizes,”Mathematics of Operation Research 13(1) (1988) 140–151. · Zbl 0658.90077 · doi:10.1287/moor.13.1.140
[9] W. Rhee and M. Talagrand, ”Optimal bin packing with items of random size -II,”SIAM Journal on Computing 18 (1989) 139–151. · Zbl 0677.90056 · doi:10.1137/0218009
[10] W. Rhee and M. Talagrand, ”Optimal bin packing with items of random size -III,”SIAM Journal on Computing 18 (1989) 473–486. · Zbl 0698.90051 · doi:10.1137/0218033
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.