On-line bin packing in linear time
Open accessThe 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
Complexity of Computer Computations
Miller, R. E., Thatcher, J. W., & Bohlinger, J. D. (1972) · Springer eBooks · doi:10.1007/978-1-4684-2001-2 · Cited by 2,789 · 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
An efficient approximation scheme for the one-dimensional bin-packing problem
Karmarkar, N. K., & Karp, R. M. (1982) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1982.61 · Cited by 479 · see citing works
Approximation Algorithms for Bin-Packing — An Updated Survey
Coffman, E. G., Garey, M. R., & Johnson, D. S. (1984) · CISM International Centre for Mechanical Sciences · doi:10.1007/978-3-7091-4338-4_3 · Cited by 433 · see citing works
A simple on-line bin-packing algorithm
Lee, C. C., & Lee, D. T. (1985) · Journal of the ACM · doi:10.1145/3828.3833 · Cited by 357 · see citing works
Self-citationNew Algorithms for Bin Packing
Yao, A. C.-C. (1980) · Journal of the ACM · doi:10.1145/322186.322187 · Cited by 286 · see citing works
Shelf Algorithms for Two-Dimensional Packing Problems
Baker, B. S., & Schwarz, J. S. (1983) · SIAM Journal on Computing · doi:10.1137/0212033 · Cited by 179 · see citing works
Algorithm Design for Computer System Design
Ausiello, G., Lucertini, M., & Serafini, P. (1984) · Courses and lectures · doi:10.1007/978-3-7091-4338-4 · Cited by 130 · 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
Self-citation
Flagged first, then by citations
Research works printed but not linked: 2
- CGJ82| Chung, F. R. K., Garey, M. R., and Johnson, D. S., On packing two-dimensional bins, SIAM J. Alg. Disc. Meth. 3 (1982), 66-76.
- Fernandez de la Vega, W. and Lueker, G. S., Bin packing can be solved within 1 + t in linear time, Combinatorica, 1 (1981), 349-355.
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
On 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
- Authors
- Ramanan, P., Brown, D. J., Lee, C. C., & Lee, D. T.
- Affiliations
- University of California, Santa Barbara (US)
- University of Illinois Urbana-Champaign (US)
- Northwestern University (US)
- ORCID
- Lee, D.T
- Venue
- Journal of Algorithms
- Publisher
- Elsevier BV
- Published
- 1989-09
- Volume
- 10
- Issue
- 3
- Pages
- 305-326
- ISSN
- 0196-6774 (ISSN-L)
- OpenAlex
- W2016393589
- Cited by
- 127
- References
- 14
- Citations by year
- 2026: 2 · 2025: 3 · 2024: 2 · 2023: 3 · 2022: 4 · 2021: 6 · 2020: 7 · 2019: 2 · 2018: 3 · 2017: 4 · 2016: 7 · 2015: 6 · 2014: 7 · 2013: 6 · 2012: 4
- FWCI
- 12.40
- Type
- journal article
- Language
- en
- Open access
- green
- hdl.handle.net
- Locations
- Journal of Algorithms (publishedVersion)
- Illinois Digital Environment for Access to Learning and Scholarship (University of Illinois at Urbana-Champaign) (submittedVersion)
- Defense Technical Information Center (DTIC) (submittedVersion)
- 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, linear-time algorithms, weight functions, heuristic 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
