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