Improved bounds for harmonic-based bin packing algorithms

AbstractThe 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