Approximation Algorithms for Bin-Packing — An Updated Survey
The DOI matches its Crossref record; 89 of the 92 references it cites were found in a registry or an index.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“However, they often show poor performance in practice39.”
From Mathematical discoveries from program search with large language models (2024) · cites this paper as [39]
Citations
Cites
(1979) · Cited by 43,841
Self-citationReducibility among Combinatorial Problems
Karp, R. M. (1972) · Complexity of Computer Computations · doi:10.1007/978-1-4684-2001-2_9 · Cited by 11,511
Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
Graham, R. L., Lawler, E. L., Lenstra, J. K., & Kan, A. H. G. R. (1979) · Annals of Discrete Mathematics · doi:10.1016/s0167-5060(08)70356-x · Cited by 5,854
Complexity of Computer Computations
(1972) · Springer eBooks · doi:10.1007/978-1-4684-2001-2 · Cited by 2,781
Bounds on Multiprocessing Timing Anomalies
Graham, R. L. (1969) · SIAM Journal on Applied Mathematics · doi:10.1137/0117039 · Cited by 2,443
A Linear Programming Approach to the Cutting-Stock Problem
Gilmore, P. C., & Gomory, R. E. (1961) · Operations Research · doi:10.1287/opre.9.6.849 · Cited by 2,024
Bounds for Certain Multiprocessing Anomalies
Graham, R. L. (1966) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1966.tb01709.x · Cited by 1,647
A Linear Programming Approach to the Cutting Stock Problem—Part II
Gilmore, P. C., & Gomory, R. E. (1963) · Operations Research · doi:10.1287/opre.11.6.863 · Cited by 1,119
Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
Johnson, D. S., Demers, A., Ullman, J. D., Garey, M. R., & Graham, R. L. (1974) · SIAM Journal on Computing · doi:10.1137/0203025 · Cited by 911
Self-citationMultistage Cutting Stock Problems of Two and More Dimensions
Gilmore, P. C., & Gomory, R. E. (1965) · Operations Research · doi:10.1287/opre.13.1.94 · Cited by 809
The NP-completeness column: An ongoing guide
Johnson, D. S. (1986) · Journal of Algorithms · doi:10.1016/0196-6774(86)90020-9 · Cited by 794
Self-citationOrthogonal Packings in Two Dimensions
Baker, B. S., Coffman, Jr., & Rivest, R. L. (1980) · SIAM Journal on Computing · doi:10.1137/0209064 · Cited by 700
Self-citationAn Application of Bin-Packing to Multiprocessor Scheduling
Coffman, E. G., Garey, M. R., & Johnson, D. S. (1978) · SIAM Journal on Computing · doi:10.1137/0207001 · Cited by 666
Self-citationAlgorithms for Scheduling Independent Tasks
Sahni, S. K. (1976) · Journal of the ACM · doi:10.1145/321921.321934 · Cited by 597
Near-optimal bin packing algorithms
Johnson, D. S. (1973) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 573
Self-citationFast algorithms for bin packing
Johnson, D. S. (1974) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(74)80026-7 · Cited by 540
Self-citationAn Algorithm for Two-Dimensional Cutting Problems
Christofides, N., & Whitlock, C. (1977) · Operations Research · doi:10.1287/opre.25.1.30 · Cited by 526
Bin packing can be solved within 1 + ε in linear time
de la Véga, W. F., & Lueker, G. S. (1981) · COMBINATORICA · doi:10.1007/bf02579456 · Cited by 510
Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms
Coffman, E. G., Garey, M. R., Johnson, D. S., & Tarjan, R. E. (1980) · SIAM Journal on Computing · doi:10.1137/0209062 · Cited by 495
Self-citationAn 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 491
Algorithms and Complexity: New Directions and Recent Results
Traub, J. F. (1976) · UCLA - Biblioteca de Ciencias y Tecnologia Felix Morales Bueno · Cited by 427
Astrom, K. J. (2002) · Proceedings of 1994 IEEE International Symposium on Information Theory · doi:10.1109/isit.1994.394967 · Cited by 397
Resource constrained scheduling as generalized bin packing
Garey, M. R., Graham, R. L., Johnson, D. S., & Yao, A. C.-C. (1976) · Journal of Combinatorial Theory Series A · doi:10.1016/0097-3165(76)90001-7 · Cited by 353
Self-citationNew Algorithms for Bin Packing
Yao, A. C.-C. (1980) · Journal of the ACM · doi:10.1145/322186.322187 · Cited by 281
Bounds for Multiprocessor Scheduling with Resource Constraints
Garey, M. R., & Graham, R. L. (1975) · SIAM Journal on Computing · doi:10.1137/0204015 · Cited by 251
Self-citationOptimal Allocation of Two-Dimensional Irregular Shapes Using Heuristic Search Methods
Albano, A., & Sapuppo, G. (1980) · IEEE Transactions on Systems, Man, and Cybernetics · doi:10.1109/tsmc.1980.4308483 · Cited by 217
On Packing Two-Dimensional Bins
Chung, F., Garey, M. R., & Johnson, D. S. (1982) · SIAM Journal on Algebraic and Discrete Methods · doi:10.1137/0603007 · Cited by 211
Self-citationThe Differencing Method of Set Partitioning
Karmarker, N., & Karp, R. M. (1983) · Cited by 207
Shelf Algorithms for Two-Dimensional Packing Problems
Baker, B. S., & Schwarz, J. S. (1983) · SIAM Journal on Computing · doi:10.1137/0212033 · Cited by 181
On a dual version of the one-dimensional bin packing problem
Assmann, S. F., Johnson, D. S., Kleitman, D. J., & Leung, J. Y. ‐. (1984) · Journal of Algorithms · doi:10.1016/0196-6774(84)90004-x · Cited by 176
Self-citationCoffman, E. G., Garey, M. R., & Johnson, D. S. (1983) · SIAM Journal on Computing · doi:10.1137/0212014 · Cited by 174
Self-citationAssembly line balancing as generalized bin packing
Wee, T. S., & Magazine, M. J. (1982) · Operations Research Letters · doi:10.1016/0167-6377(82)90046-3 · Cited by 167
A algorithm for two-dimensional packing
Baker, B. S., Brown, D. J., & Katseff, H. P. (1981) · Journal of Algorithms · doi:10.1016/0196-6774(81)90034-1 · Cited by 154
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 132
Self-citationA linear time approximation algorithm for multiprocessor scheduling
Finn, G., & Horowitz, E. (1979) · BIT Numerical Mathematics · doi:10.1007/bf01930985 · Cited by 128
Worst-Case Analysis of a Placement Algorithm Related to Storage Allocation
Chandra, A. K., & Wong, C. K. (1975) · SIAM Journal on Computing · doi:10.1137/0204021 · Cited by 124
A new proof for the first-fit decreasing bin-packing algorithm
Baker, B. S. (1985) · Journal of Algorithms · doi:10.1016/0196-6774(85)90018-5 · Cited by 121
Analysis of Several Task-Scheduling Algorithms for a Model of Multiprogramming Computer Systems
Krause, K. L., Shen, V. Y., & Schwetman, H. D. (1975) · Journal of the ACM · doi:10.1145/321906.321917 · Cited by 121
Scheduling to Maximize the Minimum Processor Finish Time in a Multiprocessor System
Deuermeyer, B. L., Friesen, D. K., & Langston, M. A. (1982) · SIAM Journal on Algebraic and Discrete Methods · doi:10.1137/0603019 · Cited by 119
Bounds on multiprocessing anomalies and related packing algorithms
Graham, R. L. (1971) · AFIPS Fall Joint Computer Conference (FJCC) · doi:10.1145/1478873.1478901 · Cited by 118
A 2.5 times optimal algorithm for packing in two dimensions
Sleator, D. D. (1980) · Information Processing Letters · doi:10.1016/0020-0190(80)90121-0 · Cited by 117
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 105
Analytical Evaluation of Hierarchical Planning Systems
Dempster, M. A. H., Fisher, M. L., Jansen, L., Lageweg, B. J., Lenstra, J. K., & Kan, A. H. G. R. (1981) · Operations Research · doi:10.1287/opre.29.4.707 · Cited by 104
Multidimensional Bin Packing Algorithms
Kou, L. T., & Markowsky, G. (1977) · IBM Journal of Research and Development · doi:10.1147/rd.215.0443 · Cited by 103
A stochastic model of bin-packing
Coffman, E. G., So, K., Hofri, M., & Yao, A. C.-C. (1980) · Information and Control · doi:10.1016/s0019-9958(80)90050-9 · Cited by 100
Self-citationA probabilistic analysis of multidimensional bin packing problems
Karp, R. M., Luby, M. G., & Marchetti-Spaccamela, A. (1984) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/800057.808693 · Cited by 89
Bin packing: Maximizing the number of pieces packed
Coffman, E. G., Leung, J. Y. ‐., & Ting, D. (1978) · Acta Informatica · doi:10.1007/bf00288885 · Cited by 88
Self-citationBounds for Some Functions Concerning Dynamic Storage Allocation
Robson, J. M. (1974) · Journal of the ACM · doi:10.1145/321832.321846 · Cited by 77
On packing squares with equal squares
Erdős, P., & Graham, R. L. (1975) · Journal of Combinatorial Theory Series A · doi:10.1016/0097-3165(75)90099-0 · Cited by 76
Worst case fragmentation of first fit and best fit storage allocation strategies
Robson, J. M. (1977) · The Computer Journal · doi:10.1093/comjnl/20.3.242 · Cited by 67
The NP-completeness column: An ongoing guide
Johnson, D. S. (1981) · Journal of Algorithms · doi:10.1016/0196-6774(81)90037-7 · Cited by 65
Self-citationA generalized bound on LPT sequencing
Coffman, E. G., & Sethi, R. (1976) · ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS) · doi:10.1145/800200.806205 · Cited by 64
Self-citationBin packing with items uniformly distributed over intervals [a,b]
Lueker, G. S. (1983) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1983.9 · Cited by 63
On the Optimality of the Probability Ranking Scheme in Storage Applications
Yue, P. C., & Wong, C. K. (1973) · Journal of the ACM · doi:10.1145/321784.321790 · Cited by 62
Performance Bounds for Orthogonal Oriented Two-Dimensional Packing Algorithms
Golan, I. (1981) · SIAM Journal on Computing · doi:10.1137/0210042 · Cited by 61
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 60
Lower bounds for on-line two-dimensional packing algorithms
Brown, D., Baker, B. S., & Katseff, H. P. (1982) · Acta Informatica · doi:10.1007/bf00264439 · Cited by 60
A Tight Asymptotic Bound for Next-Fit-Decreasing Bin-Packing
Baker, B. S., & Coffman, Jr. (1981) · SIAM Journal on Algebraic Discrete Methods · doi:10.1137/0602019 · Cited by 59
Self-citationAnalysis of Heuristics for Stochastic Programming: Results for Hierarchical Scheduling Problems
Dempster, M. A. H., Fisher, M. L., Jansen, L., Lageweg, B. J., Lenstra, J. K., & Kan, A. H. G. R. (1983) · Mathematics of Operations Research · doi:10.1287/moor.8.4.525 · Cited by 58
Record Allocation for Minimizing Expected Retrieval Costs on Drum-Like Storage Devices
Cody, R. A., & Coffman, E. G. (1976) · Journal of the ACM · doi:10.1145/321921.321933 · Cited by 57
Self-citationAn Almost-Optimal Algorithm for the Assembly Line Scheduling Problem
Kaufman, M. T. (1974) · IEEE Transactions on Computers · doi:10.1109/t-c.1974.223825 · Cited by 57
A general packing algorithm for multidimensional resource requirements
Maruyama, K., Chang, S.-K., & Tang, D. T. (1977) · International Journal of Parallel Programming · doi:10.1007/bf00999302 · Cited by 56
Probabilistic analysis for simple one-and two-dimensional bin packing algorithms
Frederickson, G. N. (1980) · Information Processing Letters · doi:10.1016/0020-0190(80)90041-1 · Cited by 49
Analysis and Design of Algorithms in Combinatorial Optimization
Ausiello, G., & Lucertini, M. (1981) · Springer eBooks · doi:10.1007/978-3-7091-2748-3 · Cited by 43
An Introduction to Combinatorial Models of Dynamic Storage Allocation
Coffman, E. G. (1983) · SIAM Review · doi:10.1137/1025074 · Cited by 43
Self-citationA bin packing algorithm with complexity O(n log n) and performance 1 in the stochastic limit
Knödel, W. (1981) · Lecture notes in computer science · doi:10.1007/3-540-10856-4_104 · Cited by 40
Probabilistic analysis of some bin-packing problems
Karmarkar, N. K. (1982) · doi:10.1109/sfcs.1982.87 · Cited by 40
Probabilistic Analysis of Bin Packing Heuristics
Ong, H. L., Magazine, M. J., & Wee, T. S. (1984) · Operations Research · doi:10.1287/opre.32.5.983 · Cited by 38
The Differencing Method of Set Partitioning
Karmarkar, N., & Karp, R. M. (1982) · UC Berkeley · Cited by 38
Two-dimensional packing: expected performance of simple level algorithms
Hofri, M. (1980) · Information and Control · doi:10.1016/s0019-9958(80)90817-7 · Cited by 37
An optimal bound for two dimensional bin packing
Kleitman, D. J., & Krieger, M. M. (1975) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1975.6 · Cited by 36
Combinatorial Analysis of an Efficient Algorithm for Processor and Storage Allocation
Coffman, E. G., & Leung, J. Y. ‐. (1979) · SIAM Journal on Computing · doi:10.1137/0208016 · Cited by 36
Self-citationBrown, D. J. (1980) · Information Processing Letters · doi:10.1016/0020-0190(80)90031-9 · Cited by 35
On the Expected Relative Performance of List Scheduling
Coffman, E. G., & Gilbert, E. N. (1985) · Operations Research · doi:10.1287/opre.33.3.548 · Cited by 35
Self-citationAn average-case analysis of bin packing with uniformly distributed item sizes
Lueker, G. S. (1982) · eScholarship (California Digital Library) · Cited by 33
A Note on Expected Makespans for Largest-First Sequences of Independent Tasks on Two Processors
Coffman, E. G., Frederickson, G. N., & Lueker, G. S. (1984) · Mathematics of Operations Research · doi:10.1287/moor.9.2.260 · Cited by 28
Self-citationTight Bounds and Probabilistic Analysis of Two Heuristics for Parallel Processor Scheduling
Loulou, R. (1984) · Mathematics of Operations Research · doi:10.1287/moor.9.1.142 · Cited by 26
Probabilistic analysis of some bin-packing problems
Karmarkar, N. K. (1982) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1982.37 · Cited by 25
Approximation Algorithms for Maximizing the Number of Squares Packed into a Rectangle
Baker, B. S., Calderbank, A. R., Coffman, E. G., & Lagarias, J. C. (1983) · SIAM Journal on Algebraic and Discrete Methods · doi:10.1137/0604039 · Cited by 22
Self-citationImproved 0/1-interchange scheduling
Langston, M. A. (1982) · BIT Numerical Mathematics · doi:10.1007/bf01934441 · Cited by 20
A class of simple stochastic online bin packing algorithms
Hoffmann, U. (1982) · Computing · doi:10.1007/bf02241699 · Cited by 18
Bin Packing with Geometric Constraints in Computer Network Design
Chandra, A. K., Hirschberg, D. S., & Wong, C. K. (1978) · Operations Research · doi:10.1287/opre.26.5.760 · Cited by 17
Performance of Heuristic Bin Packing Algorithms with Segments of Random Length
Shapiro, S. D. (1977) · Information and Computation · Cited by 12
The Effect of a Capacity Constraint on the Minimal Cost of a Partition
Wong, C. K., & Easton, M. C. (1975) · Journal of the ACM · doi:10.1145/321906.321907 · Cited by 10
Dynamic, first-fit packings in two or more dimensions
Coffman, E. G., & Gilbert, E. N. (1984) · Information and Control · doi:10.1016/s0019-9958(84)80059-5 · Cited by 10
Self-citationAn Introduction to Proof Techniques for Bin-Packing Approximation Algorithms
Coffman, E. G. (1982) · Springer eBooks · doi:10.1007/978-94-009-7801-0_14 · Cited by 8
Self-citationGardner, M. R. (1979) · Scientific American · doi:10.1038/scientificamerican1079-18 · Cited by 5
Sensitivity Analysis for Heuristic Algorithms
Friesen, D. K. (1978) · Illinois Digital Environment for Access to Learning and Scholarship (University of Illinois at Urbana-Champaign) · Cited by 3
A Counterexample to a Bin Packing Conjecture
Shearer, J. B. (1981) · SIAM Journal on Algebraic and Discrete Methods · doi:10.1137/0602034 · Cited by 1
Research works printed but not linked: 12
- Assmann, S. B., Doctoral Dissertation, Department of Mathematics, M.I.T., Cambridge, Mass. (1983).
- Biro, M. and Boros, E., “A network flow approach to non-guillotine cutting problems,” Working Paper MO/30 (1982), Computer and Automation Institute, Hungarian Academy of Sciences, Budapest.
- Brown, A. R., Optimum Packing and Depletion, American Elsevier, New York (1971).
- Garey, M. R., Graham, R. L., and Johnson, D. S., “On a number-theoretic bin packing conjecture,” Proc. 5th Hungarian Combinatorics Colloquium, North-Holland, Amsterdam (1978), 377–392.
- Golan, I., “Two orthogonal oriented algorithms for packing in two dimension,” Report 1979/311/MHM, Computer Center M.O.D., P. O. Box 2250, Haifa, Israel (1979).
- Graham, R. L., “Bounds on performnce of scheduling algorithms,” in E. G. Coffman, Jr. (ed.), Computer and Job-Shop Scheduling Theory, John Wiley & Sons, New York (1976), 165–227.
- Hofri, M., “Bin-packing: An analysis of the Next-Fit algorithm,” Tech. Rep. No. 242, Dept. of Computer Science, The Technion, Haifa, Israel (1982).
- Knuth, D. E., Fundamental Algorithms, Vol. 1, Second edition, Addison-Wesley (1973).
- Langston, M. A., Processor Scheduling with Improved Heuristic Algorithms, Doctoral dissertation, Texas A&M University, College Station, Texas (1981).
- Langston, M. A., “Improved LPT scheduling for identical processor systems,” RAIRO-Technique et Science Informatiques, 1 (1982), 69–75.
- Loulou, R., “Probabilistic behavior of optimal bin packing solutions,” Tech. Rep., Faculty of Management, McGill University, Montreal (1982).
- Schrijver, A. (ed.), Packing and Covering in Combinatorics, published by Mathematical Centre, Tweede Boerhaavestraat 49, Amsterdam (1979).
Cited by
A typology of cutting and packing problems
Dyckhoff, H. (1990) · European Journal of Operational Research · doi:10.1016/0377-2217(90)90350-k · Cited by 1,125
Search-based software engineering: Trends, techniques and applications
Harman, M., Mansouri, S. A., & Zhang, Y. (2012) · ACM Computing Surveys · doi:10.1145/2379776.2379787 · Cited by 777
“The allocation of teams to work packages in software project planing can be thought of as an application of a bin packing problem [Coffman et al. 1984].”
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
An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem
Hopper, E. M., & Turton, B. (2001) · European Journal of Operational Research · doi:10.1016/s0377-2217(99)00357-4 · Cited by 516
On genetic algorithms for the packing of polygons
Jakobs, S. (1996) · European Journal of Operational Research · doi:10.1016/0377-2217(94)00166-9 · Cited by 494
Metadata
- Authors
- Coffman, E. G., Garey, M. R., & Johnson, D. S.
- Venue
- CISM International Centre for Mechanical Sciences
- Publisher
- Springer Vienna
- Published
- 1984
- Pages
- 49-106
- ISSN
- 0254-1971 (ISSN-L)
- 2309-3706
- OpenAlex
- W1519941054
- Cited by
- 433
- References
- 92
- Citations by year
- 2026: 4 · 2025: 8 · 2024: 11 · 2023: 5 · 2022: 7 · 2021: 14 · 2020: 8 · 2019: 14 · 2018: 9 · 2017: 7 · 2016: 7 · 2015: 8 · 2014: 8 · 2013: 7 · 2012: 3
- FWCI
- 61.09
- Type
- book chapter
- Language
- en
- Open access
- closed
- Locations
- Courses and lectures (publishedVersion)
- Topics
- Physical Sciences › Engineering › Industrial and Manufacturing Engineering › Optimization and Packing Problems
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Physical Sciences › Computer Science › Computer Graphics and Computer-Aided Design › Computational Geometry and Mesh Generation
- Keywords
- bin packing, approximation algorithms, approximation ratio, scheduling, combinatorial optimization
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
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.