Resource augmentation for online bounded space bin packing
Csirik, János and Woeginger, Gerhard J. (2002) Resource augmentation for online bounded space bin packing. Journal of Algorithms, 44 (2). pp. 308-320. ISSN 0196-6774
Restricted to UT campus only: Request a copy
|Abstract:||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 ρ(b). Moreover, we prove that no online bounded space algorithm can perform better than ρ(b) in the worst case.
|Copyright:||© 2002 Elsevier|
Electrical Engineering, Mathematics and Computer Science (EEMCS)
|Link to this item:||http://purl.utwente.nl/publications/74804|
|Export this item as:||BibTeX|
Daily downloads in the past month
Monthly downloads in the past 12 months
Repository Staff Only: item control page
Metis ID: 208626