A simple on-line bin-packing algorithm
Open accessAbstract
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.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
(1979) · Cited by 43,841 · see citing works
Reducibility among Combinatorial Problems
Karp, R. M. (1972) · Complexity of Computer Computations · doi:10.1007/978-1-4684-2001-2_9 · Cited by 11,511 · see citing works
Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
Johnson, D. S., Demers, A. J., Ullman, J. D., et al. (1974) · SIAM Journal on Computing · doi:10.1137/0203025 · Cited by 922 · see citing works
Near-optimal bin packing algorithms
Johnson, D. S. (1973) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 563 · see citing works
Fast algorithms for bin packing
Johnson, D. S. (1974) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(74)80026-7 · Cited by 543 · see citing works
New Algorithms for Bin Packing
Yao, A. C.-C. (1980) · Journal of the ACM · doi:10.1145/322186.322187 · Cited by 286 · see citing works
Approximation Algorithms for Bin Packing Problems: A Survey
Garey, M. R., & Johnson, D. S. (1981) · Springer eBooks · doi:10.1007/978-3-7091-2748-3_8 · Cited by 125 · see citing works
A lower bound for on-line bin packing
Liang, F. M. (1980) · Information Processing Letters · doi:10.1016/s0020-0190(80)90077-0 · Cited by 103 · see citing works
A Lower Bound for On-Line One-Dimensional Bin Packing Algorithms.
Brown, D. J. (1979) · Illinois Digital Environment for Access to Learning and Scholarship (University of Illinois at Urbana-Champaign) · Cited by 62 · see citing works
Flagged first, then by citations
Research works printed but not linked: 1
- RECEIVED MAY 1983; REVISED OCTOBER 1984; ACCEPTED JANUARY 1985 Journal of the Association for Computing Machinery, Vol. 32, No. 3, July 1985
Cited by
Sorted by citations
Mathematical discoveries from program search with large language models
Romera-Paredes, B., Barekatain, M., Novikov, A., Balog, M., Kumar, M. P., Dupont, E., Ruiz, F. J. R., Ellenberg, J. S., Wang, P., Fawzi, O., et al. (2024) · Nature · doi:10.1038/s41586-023-06924-6 · Cited by 544 · see citing works
“Heuristics for online bin packing are well studied and several variants exist with strong worst case performance 40–45 .”
BackgroundOn the online bin packing problem
Seiden, S. S. (2002) · Journal of the ACM · doi:10.1145/585265.585269 · Cited by 310 · see citing works
Bin Packing Approximation Algorithms: Survey and Classification
Coffman, E. G., Csirik, J., Galambos, G., Martello, S., & Vigo, D. (2013) · Handbook of Combinatorial Optimization · doi:10.1007/978-1-4419-7997-1_35 · Cited by 289 · see citing works
On-line bin packing in linear time
Ramanan, P., Brown, D. J., Lee, C. C., & Lee, D. T. (1989) · Journal of Algorithms · doi:10.1016/0196-6774(89)90031-x · Cited by 127 · see citing works
Self-citationThe optimal absolute ratio for online bin packing
Balogh, J., Békési, J., Dósa, G., Sgall, J., & Stee, R. V. (2015) · Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms · doi:10.1137/1.9781611973730.94 · Cited by 17 · see citing works
- Authors
- Lee, C. C., & Lee, D. T.
- Affiliations
- Northwestern University (US)
- Venue
- Journal of the ACM
- Published
- 1985-07
- Volume
- 32
- Issue
- 3
- Pages
- 562-572
- ISSN
- 0004-5411 (ISSN-L)
- 1557-735X
- OpenAlex
- W2048628062
- Cited by
- 357
- References
- 9
- Citations by year
- 2026: 10 · 2025: 8 · 2024: 6 · 2023: 7 · 2022: 15 · 2021: 15 · 2020: 20 · 2019: 11 · 2018: 13 · 2017: 7 · 2016: 17 · 2015: 15 · 2014: 25 · 2013: 19 · 2012: 12
- FWCI
- 11.04
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- Journal of the ACM (publishedVersion)
- Funders
- National Science Foundation (8307264, 8202359)
- Northwestern University
- Topics
- Physical Sciences › Engineering › Industrial and Manufacturing Engineering › Optimization and Packing Problems
- Physical Sciences › Computer Science › Computer Networks and Communications › Optimization and Search Problems
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Keywords
- one-dimensional bin packing, worst-case ratio, lower bounds, first fit, approximation algorithms
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
