Bin packing with discrete item sizes, Part I:

Perfect packing theorems and the average case behavior of optimal packings

E.G. Coffman, C. Courcoubetis, D.S. Johnson, M.R. Garey, P.W. Shor, R.R. Weber and M. Yannikakis, SIAM J. Discrete Math, 13, 384-402, 2000.


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.

back to list of papers