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 ≥ 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 ≥ 1 we design online bounded space bin packing algorithms whose worst case ratio in this model comes arbitrarily close to a certain bound p(S) Moreover, we prove that no online bounded space algorithm can perform better than p(S) in the worst case.