A note on an open-end bin packing problem

A note on an open-end bin packing problem

0.00 Avg rating0 Votes
Article ID: iaor2003959
Country: United Kingdom
Volume: 4
Issue: 4
Start Page Number: 201
End Page Number: 207
Publication Date: Jul 2001
Journal: Journal of Scheduling
Authors: , ,
Keywords: packing
Abstract:

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 = (p1, p2, ..., pn) of n pieces, where pj denotes both the name and the size of the jth piece in L, and an infinite collection of infinite-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 find a packing that uses the minimum number of bins. In this article, we first 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 offline algorithm that is a fully polynomial approximation scheme with respect to the asymptotic worst-case ratio.

Reviews

Required fields are marked *. Your email address will not be published.