Dual bin packing with items of random sizes

Given a collection of items and a number of unit size bins, the dual bin packing problem requires finding the largest number of items that can be packed in these bins. In our stochastic model, the item sizesX ₁,,X _n are independent identically distributed according to a given probability measure. Denote byN _n =N _n (X ₁,,X _n ) the largest number of these items that can be packed in an bins, where 0<a<1 is a constant. We show thatb = lim _n E(N _n )/n exists, and that the random variable (N _n –nb)/ converges in distribution. The limit is identified as the distribution of the supremum of a certain Gaussian process cannonically attached to. This research is in part supported by NSF grant CCR-8801517 and CCR-9000611.This research is in part supported by NSF grant DMS-8801180.