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 hound 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. (C) 1996 Academic Press, Inc. References: 7
展开▼
