ON THE ASYMPTOTIC WORST-CASE BEHAVIOR OF HARMONIC FIT

In the parametric bin packing problem we must pack a list of items wit h size smaller than or equal to 1/r in a minimal number of unit-capaci ty bins. Among the approximation algorithms, the class of Harmonic Fit algorithms (HFM) plays an important role. Lee and Lee (J. Assoc. Comp ut. Mach. 32 (1985), 562-572) and Galambos (Ann. Univ. Sci. Budapest S ect. Comput. 9 (1988), 121-126) provide upper bounds for the asymptoti c 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 t he known upper bound for additional values of M, and we show that for remaining values of M the known upper hound is not tight. For the clas sical bin packing problem (r = 1), we prove an asymptotic worst case r atio of 12/7 for the case M = 4 and 1.7 for the case M = 5. We give im proved lower bounds for some interesting cases that are left open. (C) 1996 Academic Press, Inc.