@inproceedings{0f4b3ce035be48fa976965fbde903136,
title = "Resource augmentation for online bounded space bin packing (Extended abstract)",
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.",
author = "J. Csirik and G.J. Woeginger",
year = "2000",
doi = "10.1007/3-540-45022-X\_26",
language = "English",
isbn = "3-540-67715-1",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "296--304",
editor = "U. Montanari and J.D.P. Rolim and W. Welzl",
booktitle = "Automata, Languages and Programming (Proceedings 27th International Colloquium, ICALP 2000, Geneva, Switzerland, July 9-15, 2000)",
address = "Germany",
}