Eg. Coffman et al., Bin packing with discrete item sizes, part I: Perfect packing theorems andthe average case behavior of optimal packings, SIAM J DISC, 13(3), 2000, pp. 384-402
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 less than or equal to 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 --> i
nfinity the discrete distributions U{mj, mk} approach the continuous distri
bution U(0, j/k], where the item sizes are chosen uniformly from the interv
al (0,j/k]. We show that average-case behavior can differ substantially bet
ween 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 spa
ce 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. I 1. Our U{j, k} result is an applicatio
n of a general theorem of Courcoubetis and Weber [C. Courcoubetis and R.R.
Weber, Probab. Engrg. Inform. Sci., 4 (1990), pp. 447-460] that covers all
discrete distributions. Under each such distribution, the optimal expected
waste for a random list of n items must be either -(n), -(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 in
dependent combinatorial interest, and its proof is a cornerstone of the pap
er.