期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2001
卷号：2001
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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 one. We present a complete solution to this problem: For every bin size b, we design online bounded space bin packing algorithms whose worst case ratio in this model comes arbitrarily close to a certain bound R(b). Moreover, we prove that no online bounded space algorithm can perform better than R(b) in the worst case.
