A stochastic analysis of the harmonic bin-packing algorithm

One-dimensional bin-packing has many important applications such as multiprocessor scheduling, resource allocation, real-world planning, packing and scheduling. The problem is known to be NP-hard, so researchers have turned to the study of approximation algorithms which attempt to find near-optimal solutions although they do not guarantee to find an optimal solution for every instance. The harmonic (HK) algorithm, which was first proposed by Lee and Lee based on the Next Fit algorithm (NF), is one of the most important approximation algorithms. It is an O(n) time O(K) space online algorithm with a worst-case performance ratio of 1.69103. In this paper, we analyze the average-case performance of the Harmonic algorithm for pieces of correlated sizes, give the average-case performance ratio for (0, a] (a ≤ 1) uniform distributed inputs and verify these results with numerical experiments. We discuss the algorithm's performance for different constant a and K and point out that the algorithm performance improves for a-decreasing or K-increasing, especially when K is sufficiently large: the average-case performance ratio of Harmonic algorithm is 1.28987 under (0,1] uniform distribution while it improves to 1.15947... under (0,0.5] uniform distribution. Through this analysis we confirm that, with an O(K) extra space cost, the harmonic algorithm is better than Next Fit algorithm not only in worst-case performance, but also in average-case performance.