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

Rhee, Wansoo T.; Talagrand, Michel

Math. Oper. Res. 18, No. 2, 438-445 (1993).

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

Keywords:

asymptotic optimal packing ratio