ISSN:
1432-0541
Keywords:
Bin packing
;
Approximation algorithm
;
On-line algorithm
;
Worst-case performance
;
Average-case performance
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract In this paper we analyze the average-case performance of the Modified Harmonic algorithm for on-line bin packing. We first analyze the average-case performance for arbitrary distribution of item sizes over (0,1]. This analysis is based on the following result. Letf 1 andf 2 be two linear combinations of random variables {N i } i=1 k where theN i 's have a joint multinomial distribution for eachn=σ i=1 k ,N i . LetE(f 1) ≠ O andE(f 2)≠ 0. Then limn →∞E(max(f 1,f 2 ))/n = lim n →∞ max(E(f 1),E(f 2))/n. We then consider the special case when the item sizes are uniformly distributed over (0,1]. For specific values of the parameters, the Modified Harmonic algorithm turns out to be better than the other two linear-time on-line algorithms—Next Fit and Harmonic—in both the worst case as well as the average case. We also obtain optimal values for the parameters of the algorithm from the average-case standpoint. For these values of the parameters, the average-case performance ratio is less than 1.19. This compares well with the performance ratios 1.333. and 1.2865. of the Next Fit algorithm and the Harmonic algorithm, respectively.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01553906
Permalink
