A note on an open-end bin packing problem

✍ Scribed by Joseph Y.-T. Leung; Moshe Dror; Gilbert H. Young

• Publisher: Springer US
• Year: 2001
• Tongue: English
• Weight: 71 KB
• Volume: 4
• Category: Article
• ISSN: 1094-6136
• DOI: 10.1002/jos.75

✦ Synopsis

We consider a variant of the classical one-dimensional bin packing problem, which we call the open-end bin packing problem. Suppose that we are given a list L = (p 1 ; p 2 ; : : : ; pn) of n pieces, where p j denotes both the name and the size of the jth piece in L, and an inÿnite collection of inÿnite-capacity bins. A bin can always accommodate a piece if the bin has not yet reached a level of C or above, but it will be closed as soon as it reaches that level. Our goal is to ÿnd a packing that uses the minimum number of bins. In this article, we ÿrst show that the open-end bin packing problem remains strongly NP-hard. We then show that any online algorithm must have an asymptotic worst-case ratio of at least 2, and there is a simple online algorithm with exactly this ratio. Finally, we give an o ine algorithm that is a fully polynomial approximation scheme with respect to the asymptotic worst-case ratio. Copyright ? 2001 John Wiley & Sons, Ltd.