IMPROVED SPACE FOR BOUNDED-SPACE, ONLINE BIN-PACKING

The author presents a sequence of linear-time, bounded-space, on-line, bin-packing algorithms that are based on the ''HARMONIC'' algorithms H(k) introduced by Lee and Lee [J. Assoc. Comput. Mach., 32 (1985), pp . 562-572]. The algorithms in this paper guarantee the worst case perf ormance of H(k), whereas they only use O(log log k) instead of k activ e bins. For k greater-than-or-equal-to 6. the algorithms in this paper outperform all known heuristics using k active bins. For example, the author gives an algorithm that has worst case ratio less than 17/10 a nd uses only six active bins.