A simple on-line bin-packing algorithm
- 1 July 1985
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 32 (3) , 562-572
- https://doi.org/10.1145/3828.3833
Abstract
The one-dimensional on-line bin-packing problem is considered, A simple O (1)-space and O ( n )-time algorithm, called HARMONIC M , is presented. It is shown that this algorithm can achieve a worst-case performance ratio of less than 1.692, which is better than that of the O ( n )-space and O ( n log n )-time algorithm FIRST FIT. Also shown is that 1.691 … is a lower bound for all 0 (1)-space on-line bin-packing algorithms. Finally a revised version of HARMONIC M , an O ( n )-space and O ( n )- time algorithm, is presented and is shown to have a worst-case performance ratio of less than 1.636.Keywords
This publication has 5 references indexed in Scilit:
- Fast algorithms for bin packingPublished by Elsevier ,2007
- New Algorithms for Bin PackingJournal of the ACM, 1980
- A lower bound for on-line bin packingInformation Processing Letters, 1980
- Worst-Case Performance Bounds for Simple One-Dimensional Packing AlgorithmsSIAM Journal on Computing, 1974
- Reducibility among Combinatorial ProblemsPublished by Springer Nature ,1972