1996
On the Asymptotic Worst Case Behavior of Harmonic Fit
Publication
Publication
Journal of Algorithms , Volume 20 - Issue 1 p. 113- 136
In the parametric bin packing problem we must pack a list of items with size smaller than or equal to 1/r in a minimal number of unit-capacity bins. Among the approximation algorithms, the class of Harmonic Fit algorithms (HFM) plays an important role. Lee and Lee (J. Assoc. Comput. Mach. 32 (1985), 562-572) and Galambos (Ann. Univ. Sci. Budapest Sect. Comput. 9 (1988), 121-126) provide upper bounds for the asymptotic worst case ratio of HFM and show tightness for certain values of the parameter M. In this paper we provide worst case examples that meet the known upper bound for additional values of M, and we show that for remaining values of M the known upper bound is not tight. For the classical bin packing problem (r = 1), we prove an asymptotic worst case ratio of 12/7 for the case M = 4 and 1.7 for the case M = 5. We give improved lower bounds for some interesting cases that are left open.
| Additional Metadata | |
|---|---|
| doi.org/10.1006/jagm.1996.0005, hdl.handle.net/1765/58358 | |
| Journal of Algorithms | |
| Organisation | Erasmus School of Economics |
|
van Vliet, A. (1996). On the Asymptotic Worst Case Behavior of Harmonic Fit. Journal of Algorithms, 20(1), 113–136. doi:10.1006/jagm.1996.0005 |
|
