A tight lower bound for optimal bin packing

0.00 Avg rating—0 Votes

Article ID:	iaor1997697
Country:	Netherlands
Volume:	18
Issue:	3
Start Page Number:	133
End Page Number:	138
Publication Date:	Oct 1995
Journal:	Operations Research Letters
Authors:	Chao Heng-Yi, Harper Mary P., Quong Russel W.
Keywords:	bin packing

Abstract:

In this paper, the authors present an O(nlogn) algorithm to compute a tight lower bound for the one-dimensional bin packing problem. They have simulated the algorithm on randomly generated bin packing problems with item sizes drawn uniformly from (a,b], where 0•a<b•B and B is bin size. Using the present lower bound, the average error of BFD is less than 2%. For a+b≥B, the error is less than 0.003%.

Reviews

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