We consider the one-dimensional bin packing problem under the discrete uniform distributions U{j,k}, 1≤j≤k−1, in which the bin capacity is k and item sizes are chosen uniformly from the set {1,2,...,j}. Note that for 0<u=j/k≤1 this is a discrete version of the previously studied continuous uniform distribution U(0,u], where the bin capacity is 1 and item sizes are chosen uniformly from the interval (0,u]. We show that the average-case performance of heuristics can differ substantially between the two types of distributions. In particular, there is an online algorithm that has constant expected wasted space under U{j,k} for any j,k with 1≤j<k−1, whereas no online algorithm can have o(n1/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 Θ(n), Θ(n1/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. We also survey other recent results comparing the behavior of heuristics under discrete and continuous uniform distributions.
