Probabilistic analysis of a bin covering algorithm

In the bin covering problem the authors are asked to pack a list of n items, each with size no larger than one, into the maximum number of bins such that the sum of the sizes of the items in each bin is at least one. In this article they analyze the asymptotic average-case behavior of the Iterated-Lowest-Fit-Decreasing (ILFD) algorithm proposed by Assmann et al. Let OPT(X(n)) denote the maximum number of bins that can be covered by X(n) and let ILFD(X(n)) denote the number of bins covered by the ILFD algorithm. Assuming that X(n) is a random sample from an arbitrary probability measure over [0, 1], the authors show the existence of a constant and a constructible sequence such that and almost surely. Since always lies in [0, 1], it follows that as well. The authors also show that the expected values of the ratio , over all possible probability measures for lie in , the same range as the deterministic case.