Resource augmentation for online bounded space bin packing

Share/Save/Bookmark

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

[img]PDF
Restricted to UT campus only
: Request a copy
105Kb
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.
Item Type:Article
Copyright:© 2002 Elsevier
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/74804
Official URL:http://dx.doi.org/10.1016/S0196-6774(02)00202-X
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page

Metis ID: 208626