On-Line Bin Packing of Items of Random Sizes, II

This paper describes the construction of an on-line algorithm with the following property. There exist universal constants K, α such that given any probability measure μ on $[0,1]$ and a sequence X₁ , … ,Xₙ , … of items independently and identically distributed according to μ, the algorithm packs X₁ , … ,Xₙ into at most Tₙ (X₁ , … ,Xₙ ) + Kn^1 / 2 (log n)^3 / 4 unit-size bins, where Tₙ (X₁ , … ,Xₙ ) denotes the minimum number of bins needed to pack X₁ , … ,Xₙ, and does this with probability greater than or equal to 1 - Kexp ( - α (log n)^3 / 2 ). In contrast with the authors’ previous work on this problem, the algorithm is now independent of μ.