Probabilistic analysis of a heuristics for the dual bin packing problem

In this paper the authors study the probabilistic behavior of the first fit increasing heuristics for the dual bin packing problem. In this problem they seek to maximize the number of items that can be packed into m unit capacity bins. The authors show that when the items to be packed are independent and identically distributed, then the relative error of first fit increasing tends to zero in probability as the number of items tends to infinity. They also consider an on-line variant of this problem and propose a simple heuristics whose relative error tends to zero in probability as the number of items tends to infinity under the assumption that the item sizes are independently and identically distributed according to a distribution with finite mean and with zero in its compact support.