On-line bin packing with two item sizes

Gregory Gutin, Tommy Jensen, Anders Yeo

Abstract


We 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 .

Keywords


On-line algorithms; bin packing; competitive ratio

Full Text:

PDF


Algorithmic Operations Research. ISSN: 1718-3235