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

[img] PDF
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.
Item Type:Article
Copyright:© 2002 Elsevier
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:
Official URL:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page

Metis ID: 208626