Deep Performance Analysis of Refined Harmonic Bin Packing Alogrithm

摘要

Refined Harmonic(RH)is one of the best on-line bin packing algorithms.The algorithm was first proposed by Lee&Leen in 1985 and the upper bouund 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 is 1.28243... under the uniform distribution.