文章基本信息

标题：Resource augmentation for online bounded space bin packing
本地全文：下载
作者：Gerhard J. Woeginger
期刊名称：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.
关键词：bin packing , competitive analysis , Online algorithm , resource augmentation