On-line bin packing with two item sizes

Gregory Gutin; Tommy Jensen; Anders Yeo

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

Download Citation

Issue

Vol. 1 No. 2 (2006)

Section

Articles

License

The copyright of the submitted article is hereby transferred to “Preeminent Academic Facets Inc. (the “publisher”) to the extent possible by the laws in the respective countries of the author(s). The author(s) retain all other rights including the following: 1. Any patents and trademark rights. 2. Right to post a pre-print version of the paper on the author’s personal website which is not used for commercial purposes. The author(s) warrant that the work is original, it has not been published elsewhere, it is not currently under consideration for publication in any form, and it does not infringe any copyright laws. The signing author or agent further warrants that all authors, if applicable, have been informed of the terms of this agreement and obtained the approval and authority to sign the agreement.