On-line bin packing with two item sizes

Authors

  • 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

Keywords:

On-line algorithms, bin packing, competitive ratio

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 .

Downloads

Published

2006-06-30

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

Issue

Section

Articles