@inproceedings{e443a60a2b744bd7b0c94c724b5c008b,
title = "Two-bounded-space bin packing revisited",
abstract = "We analyze approximation algorithms for bounded-space bin packing by comparing them against the optimal bounded-space packing (instead of comparing them against the globally optimal packing that does not necessarily satisfy the bounded-space constraint). For 2-bounded-space bin packing we construct a polynomial time offline approximation algorithm with asymptotic worst case ratio 3/2, and we show a lower bound of 5/4 for this scenario. We show that no 2-bounded-space online algorithm can have an asymptotic worst case ratio better than 4/3.",
author = "M. Chrobak and J. Sgall and G.J. Woeginger",
year = "2011",
doi = "10.1007/978-3-642-23719-5_23",
language = "English",
isbn = "978-3-642-23718-8",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "263--274",
editor = "C. Demetrescu and M.H. Halldorsson",
booktitle = "Algorithms - ESA 2011 (19th Annual European Symposium, Ljubljana, Slovenia, September 5-9, 2011. Proceedings)",
address = "Germany",
}