Improved bounds for harmonic-based bin packing algorithms

Improved bounds for harmonic-based bin packing algorithms

0.00 Avg rating0 Votes
Article ID: iaor19921406
Country: Netherlands
Volume: 34
Start Page Number: 203
End Page Number: 227
Publication Date: Nov 1991
Journal: Discrete Applied Mathematics
Authors:
Keywords: bin packing
Abstract:

The modified harmonic bin packing algorithm, and Hu and Kahng’s unnamed algorithm, are variations of the harmonic bin packing algorithm which are still on-line and run in linear time, but use linear rather than constant working storage to lower the asymptotic performance bound from 1.6910 to 1.612 and 1.6066, respectively. In this paper, further improvements lower the bound to 1.5888. It then is shown that improvements of the type introduced in this paper only can do as well as 1.5874, and hence that additional significant improvements to this particular approach are impossible. Finally, some ideas on how a better algorithm might operate are discussed.

Reviews

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