We discuss various aspects of a conjecture that spans Analysis, Probability and Combinatorics. We find it interesting enough to offer a $1000 prize for a solution of any of the main problems.

Consider independent random variables $X_1 , \ldots ,X_n $ uniformly distributed over $[0,1]$, and denote by $B_n $ the number of bins needed to pack items of these sizes using the best-fit decreasing algorithm. We prove that the random variable $n^{{{ - 1} / 2}} $ converges in distribution to a nonnormal limit. The method consists of showing that the patterns created by the algorithm exhibit some kind of convergence.

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

Consider a probability measure $\mu $ on $[0,1]$ and independent random variables $X_1 , \cdots ,X_n $, distributed according to $\mu $. Let $Q_n (X_1 , \cdots ,X_n )$ be the minimum number of unit-size bins needed to pack items of size $X_1 , \cdots ,X_n $. In this paper it is proven that ${{|E(Q_n (X_1 , \cdots X_n ))} / {n - c(\mu )| \leqq K((\log n)/n)^{1/2}}} $, where K is a universal constant and $c(\mu )$ depends on $\mu $, ${{c(\mu ) = \lim _{n \to \infty } E(Q_n )} / {n}}$.

Consider a probability measure $\mu $ on $[0,1]$ and independent random variables $X_1 , \cdots ,X_n $ distributed according to $\mu $. Let $Q_n = Q_n (X_1 , \cdots ,X_n )$ be the minimum number of unit-size bins needed to pack items of size $X_1 , \cdots ,X_n $. Let $c(\mu ) = \lim _{n \to \infty } {{E(Q_n )} / n}$. In this paper it is proved that the random variable ${{(Q_n - nc(\mu ))} / {\sqrt n }}$ converges in distribution. The limit is identified as a distribution of the supremum of a certain Gaussian process canonically attached to $\mu $.

Consider a probability measure $\mu $ on $[0,1]$ and independent random variables $X_1 , \cdots ,X_n $ distributed according to $\mu $. Let $Q_n = Q_n (X_1 , \cdots ,X_n )$ be the largest number of unit-size bins that can be covered by items of size $X_1 , \cdots ,X_n $. The properties of $Q_n $ are investigated in the spirit of our work on optimal bin packing with items of random sizes. While the covering problem has many similarities with the packing problem, it turns out to be significantly harder.

Consider a probability measure $\mu $ on $[0,1]$ and an independent sequence of random variables $X_1 , \cdots ,X_n , \cdots $ distributed according to $\mu $. No regularity assumptions are made on $\mu $. Denote by $B(X_1 , \cdots ,X_n )$ the number of unit-size bins that are used by Best Fit Decreasing to pack items of size $X_1 , \cdots ,X_n $. The existence of a constant $b(\mu )$ is proven such that for each $\varepsilon > 0,$\[ \sum\limits_{n \geqq 1} {P( \left|n^{ - 1} B \left(X_1 , \cdots X_n \right) - b(\mu ) \right| \geqq \varepsilon )} < \infty . \]

Consider a probability measure $\mu $ on $[0,1]$ and an independent sequence of random variables $X_1 , \cdots ,X_n , \cdots $ distributed according to $\mu $. No regularity assumptions are made on $\mu $. Denote by $F_n (X_1 , \cdots ,X_n )$ the number of unit-size bins that are used by First Fit Decreasing to pack $X_1 , \cdots ,X_n $. The existence of a constant $f(\mu )$ is proven such that for each $\varepsilon > 0$, we have \[\sum\limits_{n \geqq 1} {P\left( \left|n^{ - 1} F_n \left(X_1 , \cdots X_n \right) - f(\mu ) \right| \geqq \varepsilon \right)} < \infty .\]

A probability distribution μ on [0, 1] allows perfect packing if n items of size X 1 , … , X n , independent and identically distributed according to μ can be packed in unit size bins in such a way that the expected wasted space is o ( n ). A large class of distributions that allow perfect packing is exhibited. As a corollary, the intervals [ a, b ] for which the uniform distribution on [ a, b ] allows perfect packing are determined.