Approximation algorithms for extensible bin packing

Approximation algorithms for extensible bin packing

0.00 Avg rating0 Votes
Article ID: iaor20081501
Country: United Kingdom
Volume: 9
Issue: 1
Start Page Number: 63
End Page Number: 69
Publication Date: Feb 2006
Journal: Journal of Scheduling
Authors: ,
Keywords: combinatorial optimization
Abstract:

In a variation of bin packing called extensible bin packing, the number of bins is specified as part of the input, and bins may be extended to hold more than the usual unit capacity. The cost of a bin is 1 if it is not extended, and the size if it is extended. The goal is to pack a set of items of given sizes into the specified number of bins so as to minimize the total cost. Adapting ideas of Grötschel et al., Karmarkar & Karp and Murgolo, we give a fully polynomial time asymptotic approximation scheme for extensible bin packing. We close with comments on the complexity of obtaining stronger results.

Reviews

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