Email this article 
Hide
Show allOn-line bin packing with two item sizes
Abstract
We study the on-line bin packing problem (BPP). In BPP, we are given a sequence B of items 2-1.gif)
and a sequence of their sizes 2-2.gif)
(each size 2-3.gif)
) and are required to pack the items into a minimum number of unit-capacity bins. Let 2-4.gif)
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 2-5.gif)
. We also obtain an exact formula for when 2-6.gif)
. This result extends the result of Faigle, Kern and Turan (1989) that 2-9.gif)
for 2-7.gif)
and 2-8.gif)
for any fixed nonnegative 2-10.gif)
.
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 .