On-line bin packing with two item sizes
Keywords:On-line algorithms, bin packing, competitive ratio
AbstractWe study the on-line bin packing problem (BPP). In BPP, we are given a sequence B of items and a sequence of their sizes (each size ) and are required to pack the items into a minimum number of unit-capacity bins. Let be the minimal asymptotic competitive ratio of an on-line algorithm in the case when all items are only of two different sizes α and ß. We prove that . We also obtain an exact formula for when . This result extends the result of Faigle, Kern and Turan (1989) that for and for any fixed nonnegative .
How to Cite
Gutin, G., Jensen, T., & Yeo, A. (2006). On-line bin packing with two item sizes. Algorithmic Operations Research, 1(2). Retrieved from https://journals.lib.unb.ca/index.php/AOR/article/view/667