## 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.

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.

**back to list of papers**

papers