Vol 1 No 2 (2006)
Articles

On-line bin packing with two item sizes

Gregory Gutin
Department of Computer Science, Royal Holloway, University of London
Tommy Jensen
Department of Computer Science, Royal Holloway, University of London
Anders Yeo
Department of Computer Science, Royal Holloway, University of London
Published June 30, 2006
Keywords
  • On-line algorithms,
  • bin packing,
  • competitive ratio
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

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 .