Bin Packing With Discrete Item Sizes, Part I: Perfect Packing Theorems and the Average Case Behavior of Optimal Packings

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 = 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 --> inf the discrete distributions U {mj, mk} approach the continuous distribution {O, j/k], where the item sizes are chosen uniformly from the interval (O, 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 sup (1/2)) expected waste under U/(O,u] for any O 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 sup (1/2)), or O(1), depending on whether certain 'perfect' packing 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.