Abstract
We consider the one-dimensional bin packing problem with unit-capacity bins and item sizes chosen according to the discrete uniform distribution U{j,k}, 1<j<=k; where each item size in {1/k,2/k,...,j/k} has probability 1/j of being chosen. Note that for fixed j,k as m tends to infinity the discrete distributions U{mj,mk} approach the continuous distribution U(0,j/k], where the item sizes are chosen uniformly from the interval (0,j/k]. We show that average-case behavior can differ substantially between the two types of distributions. In particular, for all j,k with j<k-1 there exist on-line algorithms that have constant expected wasted space under U{j,k}, whereas no on-line algorithm has even o(n^{1/2}) expected waste under U(0,u] for any 0<u<=1. Our U{j,k} result is an application of a general theorem of Courcoubetis and Weber that covers all discrete distributions. Under each such distribution, the optimal expected waste for a random list of n items must be either Theta(n), Theta(n^{1/2}), or O(1), depending on whether certain "perfect packings" exist. The Perfect Packing Theorem needed for the U{j,k} distributions is an intriguing result of independent combinatorial interest, and its proof is a cornerstone of the paper.