Resource augmentation for online bounded space bin packing

We study online bounded space bin packing in the resource augmentation model of competitive analysis. In this model, the online bounded space packing algorithm has to pack a list L of items in (0, 1] into a small number of bins of size b greater than or equal to 1. Its performance is measured by comparing the produced packing against the optimal offline packing of the list L into bins of size 1. We present a complete solution to this problem: For every bin size b greater than or equal to 1, we design online bounded space bin packing algorithms whose worst case ratio in this model comes arbitrarily close to a certain bound rho(b). Moreover, we prove that no online bounded space algorithm can perform better than rho(b) in the worst case.