Deep Performance Analysis of Refined Harmonic Bin Packing Algorithm

Refined Harmonic (RH) is one ofthe best on-line bin packing algorithms. The algorithm was firstproposed by Lee&Lee in 1985 and the upper bound of the worst-caseperformance ratio has been proved to be 1.63596... . In this paper,it is proved that 1.63596... is also the lower bound. The averageperformance of RH is also studied for the first time. It is shownthat the average-case performance ratio of RH is 1.28243...under the uniform distribution.