@article{Gutin_Jensen_Yeo_2006, title={On-line bin packing with two item sizes}, volume={1}, url={https://journals.lib.unb.ca/index.php/AOR/article/view/667}, abstractNote={We study the on-line bin packing problem (BPP). In BPP, we are given a sequence B of items <img src="/static_content/AOR/vol1(2)2-1.gif" alt="" /> and a sequence of their sizes <img src="/static_content/AOR/vol1(2)2-2.gif" alt="" /> (each size <img src="/static_content/AOR/vol1(2)2-3.gif" alt="" />) and are required to pack the items into a minimum number of unit-capacity bins. Let <img src="/static_content/AOR/vol1(2)2-4.gif" alt="" /> 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 <img src="/static_content/AOR/vol1(2)2-5.gif" alt="" />. We also obtain an exact formula for <img src="/static_content/AOR/vol1(2)2-4.gif" alt="" /> when <img src="/static_content/AOR/vol1(2)2-6.gif" alt="" />. This result extends the result of Faigle, Kern and Turan (1989) that <img src="/static_content/AOR/vol1(2)2-9.gif" alt="" /> for <img src="/static_content/AOR/vol1(2)2-7.gif" alt="" /> and <img src="/static_content/AOR/vol1(2)2-8.gif" alt="" /> for any fixed nonnegative <img src="/static_content/AOR/vol1(2)2-10.gif" alt="" />.}, number={2}, journal={Algorithmic Operations Research}, author={Gutin, Gregory and Jensen, Tommy and Yeo, Anders}, year={2006}, month={Jun.} }