Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR01-085 | 1st October 2001 00:00

Resource augmentation for online bounded space bin packing


Authors: Gerhard J. Woeginger
Publication: 27th November 2001 15:58
Downloads: 1960


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.

ISSN 1433-8092 | Imprint