On online bin packing with LIB constraints

✍ Scribed by Leah Epstein

• Publisher: John Wiley and Sons
• Year: 2009
• Tongue: English
• Weight: 119 KB
• Volume: 56
• Category: Article
• ISSN: 0894-069X
• DOI: 10.1002/nav.20383

✦ Synopsis

Abstract

In many applications of packing, the location of small items below large items, inside the packed boxes, is forbidden. We consider a variant of the classic online one‐dimensional bin packing, in which items allocated to each bin are packed there in the order of arrival, satisfying the condition above. This variant is called online bin packing problem with LIB (larger item in the bottom) constraints. We give an improved analysis of First Fit showing that its competitive ratio is at most
$ {5 \over 2} = 2.5$, and design a lower bound of 2 on the competitive ratio of any online algorithm. In addition, we study the competitive ratio of First Fit as a function of an upper bound $ {1 \over d} $
(where d is a positive integer) on the item sizes. Our upper bound on the competitive ratio of First Fit tends to 2 as d grows, whereas the lower bound of two holds for any value of d. Finally, we consider several natural and well known algorithms, namely, Best Fit, Worst Fit, Almost Worst Fit, and Harmonic, and show that none of them has a finite competitive ratio for the problem. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2009