Deep Performance Analysis of Refined Harmonic Bin Packing Algorithm

摘要

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