On online bin packing with LIB constraints

Leah Epstein

Naval Research Logistics (NRL), 2009, vol. 56, issue 8, 780-786

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

Date: 2009
References: View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://doi.org/10.1002/nav.20383

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navres:v:56:y:2009:i:8:p:780-786

Access Statistics for this article

More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().