×

On line bin packing with items of random size. (English) Zbl 0778.90046

Summary: Consider an i.i.d. sequence of random variables \(X_ 1,\dots,X_ n\) distributed according to a given distribution \(\mu\) on [0,1]. Let \(c(\mu)\) be the asymptotic optimal packing ratio, \(c(\mu)=\lim_{n\to\infty} ET_ n/n\), where \(T_ n\) is the minimum number of unit size bins needed to pack \(X_ 1,\dots,X_ n\). We prove the existence of an on line algorithm, dependent on \(\mu\), that packs \(X_ 1,\dots,X_ n\) in \(nc(\mu)+O(n^{1/2}(\log n)^{3/2})\) bins.

MSC:

90C15 Stochastic programming
90C27 Combinatorial optimization
90C60 Abstract computational complexity for mathematical programming problems
PDFBibTeX XMLCite
Full Text: DOI