An efficient algorithm for bin stretching

A sequence of items that can be packed into mm bins of unit size has to be assigned online to the bins minimizing the stretching factor, i.e., to stretch the bin sizes as little as possible such that the items fit into the bins. We present an elementary algorithm with stretching factor 11/7 improving the best known algorithm by Cheng et al. (2005) [5] with a stretching factor of 1.6. Our algorithm uses simple but efficient techniques of grouping the bins in batches of similar structure.