Improved Space for Bounded-Space, On-Line Bin-Packing
Author:
- Gerhard WoegingerGWGerhard Woeginger
- 1 November 1993
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 6 (4) , 575-581
Abstract
The author presents a sequence of linear-time, bounded-space, on-line, bin-packing algorithms that are based on the “HARMONIC” algorithms ${\text{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 performance of ${\text{H}}_k $, whereas they only use $O ( \log \log k )$ instead of k active bins. For $k\geqq 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 and uses only six active bins.
Keywords
This publication has 5 references indexed in Scilit:
- Tight Worst-Case Performance Bounds for Next-k-Fit Bin PackingSIAM Journal on Computing, 1993
- A probabilistic analysis of the next fit decreasing bin packing heuristicOperations Research Letters, 1986
- A simple on-line bin-packing algorithmJournal of the ACM, 1985
- Fast algorithms for bin packingJournal of Computer and System Sciences, 1974
- On Certain Nonlinear Recurring SequencesThe American Mathematical Monthly, 1963