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.
|Title of host publication||Algorithms - ESA 2011 (19th Annual European Symposium, Ljubljana, Slovenia, September 5-9, 2011. Proceedings)|
|Editors||C. Demetrescu, M.H. Halldorsson|
|Place of Publication||Berlin|
|Publication status||Published - 2011|
|Name||Lecture Notes in Computer Science|