The DOI matches its Crossref record.
Combinatorial Optimization: Algorithms and Complexity.
Abstract
This clearly written , mathematically rigorous text includes a novel algorithmic exposition of the simplex method and also discusses the Soviet ellipsoid algorithm for linear programming; efficient algorithms for network flow, matching, spanning trees, and matroids; the theory of NP-complete problems; approximation algorithms, local search heuristics for NPcomplete problems, more. All chapters are supplemented by thoughtprovoking problems. A useful work for graduate-level students with backgrounds in computer science, operations research, and electrical engineering. Mathematicians wishing a self-contained introduction need look no further.—American Mathematical Monthly. 1982 ed.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cited by
Future paths for integer programming and links to artificial intelligence
Glover, F. (1986) · Computers & Operations Research · doi:10.1016/0305-0548(86)90048-1 · Cited by 4,181
Metaheuristics in combinatorial optimization: Overview and conceptual comparison
Blum, C., & Roli, A. (2003) · ACM Computing Surveys · doi:10.1145/937503.937505 · Cited by 3,236
Greedy Randomized Adaptive Search Procedures
Feo, T. A., & Resende, M. G. C. (1995) · Journal of Global Optimization · doi:10.1007/bf01096763 · Cited by 2,778
Metaheuristics in Combinatorial Optimization
Gendreau, M., & Potvin, J.-Y. (2005) · Annals of Operations Research · doi:10.1007/s10479-005-3971-7 · Cited by 2,338
Greedy Randomized Adaptive Search Procedures
Resende, M. G. C., & Ribeiro, C. C. (2006) · International Series in Operations Research & Management Science · doi:10.1007/0-306-48056-5_8 · Cited by 2,310
Ant colony optimization theory: A survey
Dorigo, M., & Blum, C. (2005) · Theoretical Computer Science · doi:10.1016/j.tcs.2005.05.020 · Cited by 2,295
Centroidal Voronoi Tessellations: Applications and Algorithms
Du, Q., Faber, V., & Gunzburger, M. (1999) · SIAM Review · doi:10.1137/s0036144599352836 · Cited by 2,244
Variable neighborhood search: Principles and applications
Hansen, P., & Mladenović, N. (2001) · European Journal of Operational Research · doi:10.1016/s0377-2217(00)00100-4 · Cited by 1,902
A new approach to the maximum-flow problem
Goldberg, A. V., & Tarjan, R. E. (1988) · Journal of the ACM · doi:10.1145/48014.61051 · Cited by 1,882
A Consistent Metric for Performance Evaluation of Multi-Object Filters
Schuhmacher, D., Vo, B.-T., & Vo, B.-N. (2008) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2008.920469 · Cited by 1,855
Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization
Parrilo, P. A. (2000) · doi:10.7907/2k6y-ch43 · Cited by 1,802
Partitioning Sparse Matrices with Eigenvectors of Graphs
Pothen, A., Simon, H. D., & Liou, K.-P. (1990) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/0611030 · Cited by 1,684
Invitation to Fixed-Parameter Algorithms
Niedermeier, R. (2006) · doi:10.1093/acprof:oso/9780198566076.001.0001 · Cited by 1,668
Quantum computations: algorithms and error correction
Kitaev, A. Y. (1997) · Russian Mathematical Surveys · doi:10.1070/rm1997v052n06abeh002155 · Cited by 1,424
Just relax: convex programming methods for identifying sparse signals in noise
Tropp, J. A. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.864420 · Cited by 1,407
Static scheduling algorithms for allocating directed task graphs to multiprocessors
Kwok, Y.-K., & Ahmad, I. (1999) · ACM Computing Surveys · doi:10.1145/344588.344618 · Cited by 1,314
Ant colony optimization: Introduction and recent trends
Blum, C. (2005) · Physics of Life Reviews · doi:10.1016/j.plrev.2005.10.001 · Cited by 1,308
The Design of Approximation Algorithms
Williamson, D. P., & Shmoys, D. B. (2011) · Cambridge University Press eBooks · doi:10.1017/cbo9780511921735 · Cited by 1,301
A shortest augmenting path algorithm for dense and sparse linear assignment problems
Jonker, R., & Volgenant, A. (1987) · Computing · doi:10.1007/bf02278710 · Cited by 1,230
Reduction Techniques for Instance-Based Learning Algorithms
Wilson, D. R., & Martinez, T. R. (2000) · Machine Learning · doi:10.1023/a:1007626913721 · Cited by 1,182
Job Shop Scheduling by Simulated Annealing
van Laarhoven, P. J. M., Aarts, E. H. L., & Lenstra, J. K. (1992) · Operations Research · doi:10.1287/opre.40.1.113 · Cited by 1,123
Integer and combinatorial optimization
(1999) · Computers & Mathematics with Applications · doi:10.1016/s0898-1221(99)91259-2 · Cited by 1,117
Hand, D. J. (2007) · Drug Safety · doi:10.2165/00002018-200730070-00010 · Cited by 1,044
The traveling salesman problem: An overview of exact and approximate algorithms
Laporte, G. (1992) · European Journal of Operational Research · doi:10.1016/0377-2217(92)90138-y · Cited by 971
A tutorial on cross-layer optimization in wireless networks
Lin, X., Shroff, N. B., & Srikant, R. (2006) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2006.879351 · Cited by 833
Semi-Supervised and Unsupervised Extreme Learning Machines
Huang, G., Song, S., Gupta, J. N. D., & Wu, C. (2014) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2014.2307349 · Cited by 797
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-citationHigh-throughput ethomics in large groups of Drosophila
Branson, K., Robie, A. A., Bender, J., Perona, P., & Dickinson, M. H. (2009) · Nature Methods · doi:10.1038/nmeth.1328 · Cited by 786
On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems
Amaldi, E., & Kann, V. (1998) · Theoretical Computer Science · doi:10.1016/s0304-3975(97)00115-1 · Cited by 753
A Model of Text for Experimentation in the Social Sciences
Roberts, M. E., Stewart, B. M., & Airoldi, E. M. (2016) · Journal of the American Statistical Association · doi:10.1080/01621459.2016.1141684 · Cited by 728
Reinforcement learning for combinatorial optimization: A survey
Mazyavkina, N., Sviridov, S., Ivanov, S., & Burnaev, E. (2021) · Computers & Operations Research · doi:10.1016/j.cor.2021.105400 · Cited by 723
Optimal Matching for Observational Studies
Rosenbaum, P. R. (1989) · Journal of the American Statistical Association · doi:10.1080/01621459.1989.10478868 · Cited by 715
Johnson, D. S., Papadimitriou, C. H., & Yannakakis, M. (1988) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(88)90046-3 · Cited by 705
Self-citationMemetic algorithms and memetic computing optimization: A literature review
Neri, F., & Cotta, C. (2012) · Swarm and Evolutionary Computation · doi:10.1016/j.swevo.2011.11.003 · Cited by 680
Clustering ensembles: models of consensus and weak partitions
Topchy, A., Jain, A. K., & Punch, W. (2005) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2005.237 · Cited by 675
Metaheuristics: A bibliography
Osman, I. H., & Laporte, G. (1996) · Annals of Operations Research · doi:10.1007/bf02125421 · Cited by 672
The Complexity of Multiterminal Cuts
Dahlhaus, E., Johnson, D. S., Papadimitriou, C. H., Seymour, P. D., & Yannakakis, M. (1994) · SIAM Journal on Computing · doi:10.1137/s0097539792225297 · Cited by 662
Self-citationA survey of very large-scale neighborhood search techniques
Ahuja, R. K., Ergun, Ö., Orlin, J. B., & Punnen, A. P. (2002) · Discrete Applied Mathematics · doi:10.1016/s0166-218x(01)00338-9 · Cited by 643
A taxonomy of problems with fast parallel algorithms
Cook, S. A. (1985) · Information and Control · doi:10.1016/s0019-9958(85)80041-3 · Cited by 641
The auction algorithm: A distributed relaxation method for the assignment problem
Bertsekas, D. P. (1988) · Annals of Operations Research · doi:10.1007/bf02186476 · Cited by 634
On the Complexity of Cooperative Solution Concepts
Deng, X., & Papadimitriou, C. H. (1994) · Mathematics of Operations Research · doi:10.1287/moor.19.2.257 · Cited by 629
Self-citationA Survey on Shape Correspondence
van Kaick, O., Zhang, H., Hamarneh, G., & Cohen‐Or, D. (2011) · Computer Graphics Forum · doi:10.1111/j.1467-8659.2011.01884.x · Cited by 606
Parallel Spectral Clustering in Distributed Systems
Chen, W.-Y., Song, Y., Bai, H., Lin, C.-J., & Chang, E. Y. (2011) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2010.88 · Cited by 603
Ma, J., Zhao, J., Jiang, J., Zhou, H., & Guo, X. (2019) · International Journal of Computer Vision · doi:10.1007/s11263-018-1117-z · Cited by 601
Social Media Mining: An Introduction
Zafarani, R., Abbasi, M. A., & Liu, H. (2014) · Cambridge University Press eBooks · doi:10.1017/cbo9781139088510 · Cited by 592
The dynamic berth allocation problem for a container port
Imai, A., Nishimura, E., & Papadimitriou, S. (2001) · Transportation Research Part B: Methodological · doi:10.1016/s0191-2615(99)00057-0 · Cited by 577
Park, K., & Lee, H. (2001) · Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications · doi:10.1145/383059.383061 · Cited by 572
Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning
Morrison, D. R., Jacobson, S. H., Sauppe, J. J., & Sewell, E. C. (2016) · Discrete Optimization · doi:10.1016/j.disopt.2016.01.005 · Cited by 563
Joint Embedding Learning and Sparse Regression: A Framework for Unsupervised Feature Selection
Hou, C., Nie, F., Li, X., Yi, D., & Wu, Y. (2014) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2013.2272642 · Cited by 554
New Search Spaces for Sequencing Problems with Application to Job Shop Scheduling
Storer, R. H., Wu, S. D., & Vaccari, R. (1992) · Management Science · doi:10.1287/mnsc.38.10.1495 · Cited by 546
Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
Chor, B., & Goldreich, O. (1988) · SIAM Journal on Computing · doi:10.1137/0217015 · Cited by 544
Network of time-multiplexed optical parametric oscillators as a coherent Ising machine
Marandi, A., Wang, Z., Takata, K., Byer, R. L., & Yamamoto, Y. (2014) · Nature Photonics · doi:10.1038/nphoton.2014.249 · Cited by 541
The job shop scheduling problem: Conventional and new solution techniques
Błażewicz, J., Domschke, W., & Pesch, E. (1996) · European Journal of Operational Research · doi:10.1016/0377-2217(95)00362-2 · Cited by 536
ETSAP-TIAM: the TIMES integrated assessment model Part I: Model structure
Loulou, R., & Labriet, M. (2008) · Computational Management Science · doi:10.1007/s10287-007-0046-z · Cited by 531
Study on density peaks clustering based on k-nearest neighbors and principal component analysis
Du, M., Ding, S., & Jia, H. (2016) · Knowledge-Based Systems · doi:10.1016/j.knosys.2016.02.001 · Cited by 520
Gromov–Wasserstein Distances and the Metric Approach to Object Matching
Mémoli, F. (2011) · Foundations of Computational Mathematics · doi:10.1007/s10208-011-9093-5 · Cited by 515
Kasturi, R., Goldgof, D., Soundararajan, P., Manohar, V., Garofolo, J., Bowers, R., Boonstra, M., Korzhova, V., & Zhang, J. (2009) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2008.57 · Cited by 497
Prototype and Feature Selection by Sampling and Random Mutation Hill Climbing Algorithms
Skalak, D. B. (1994) · Machine Learning Proceedings 1994 · doi:10.1016/b978-1-55860-335-6.50043-x · Cited by 486
Interior path following primal-dual algorithms. part I: Linear programming
Monteiro, R. D. C., & Adler, I. (1989) · Mathematical Programming · doi:10.1007/bf01587075 · Cited by 486
Efficient algorithms for finding maximum matching in graphs
Galil, Z. (1986) · ACM Computing Surveys · doi:10.1145/6462.6502 · Cited by 461
A Gentle Introduction to Memetic Algorithms
Moscato, P., & Cotta, C. (2006) · International Series in Operations Research & Management Science · doi:10.1007/0-306-48056-5_5 · Cited by 457
Hulshof, P. J. H., Kortbeek, N., Boucherie, R. J., Hans, E. W., & Bakker, P. J. M. (2012) · Health Systems · doi:10.1057/hs.2012.18 · Cited by 429
Blum, C. (2005) · Computers & Operations Research · doi:10.1016/j.cor.2003.11.018 · Cited by 421
Auction algorithms for network flow problems: A tutorial introduction
Bertsekas, D. P. (1992) · Computational Optimization and Applications · doi:10.1007/bf00247653 · Cited by 421
A generalized S-D assignment algorithm for multisensor-multitarget state estimation
Deb, S., Yeddanapudi, M., Pattipati, K., & Bar-Shalom, Y. (1997) · IEEE Transactions on Aerospace and Electronic Systems · doi:10.1109/7.575891 · Cited by 415
Faster Scaling Algorithms for Network Problems
Gabow, H. N., & Tarjan, R. E. (1989) · SIAM Journal on Computing · doi:10.1137/0218069 · Cited by 414
Optimal Power Flow Using Tabu Search Algorithm
Abido, M. A. (2002) · Electric Power Components and Systems · doi:10.1080/15325000252888425 · Cited by 414
An Efficient Earth Mover's Distance Algorithm for Robust Histogram Comparison
Ling, H., & Okada, K. (2007) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2007.1058 · Cited by 414
The Traveling Salesman Problem with Distances One and Two
Papadimitriou, C. H., & Yannakakis, M. (1993) · Mathematics of Operations Research · doi:10.1287/moor.18.1.1 · Cited by 412
Self-citationQuantized incremental algorithms for distributed optimization
Rabbat, M. G., & Nowak, R. D. (2005) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2005.843546 · Cited by 408
Bi, S., Huang, L., Wang, H., & Zhang, Y.-J. A. (2021) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2021.3085319 · Cited by 407
Osaba, E., Villar-Rodriguez, E., Del Ser, J., Nebro, A. J., Molina, D., LaTorre, A., Suganthan, P. N., Coello Coello, C. A., & Herrera, F. (2021) · Swarm and Evolutionary Computation · doi:10.1016/j.swevo.2021.100888 · Cited by 406
On implementing 2D rectangular assignment algorithms
Crouse, D. F. (2016) · IEEE Transactions on Aerospace and Electronic Systems · doi:10.1109/taes.2016.140952 · Cited by 405
Data structures for weighted matching and nearest common ancestors with linking
Gabow, H. N. (1990) · Symposium on Discrete Algorithms · doi:10.5555/320176.320229 · Cited by 398
Swarm Intelligence in Optimization
Blum, C., & Li, X. (2008) · Natural Computing Series · doi:10.1007/978-3-540-74089-6_2 · Cited by 396
Image segmentation with a bounding box prior
Lempitsky, V., Kohli, P., Rother, C., & Sharp, T. (2009) · 2009 IEEE 12th International Conference on Computer Vision · doi:10.1109/iccv.2009.5459262 · Cited by 390
Image Clustering Using Local Discriminant Models and Global Integration
Yang, Y., Xu, D., Nie, F., Yan, S., & Zhuang, Y. (2010) · IEEE Transactions on Image Processing · doi:10.1109/tip.2010.2049235 · Cited by 389
Markenscoff, X., Ni, L., & Papadimitriou, C. H. (1990) · The International Journal of Robotics Research · doi:10.1177/027836499000900102 · Cited by 385
Self-citationCaetano, T. S., McAuley, J. J., Cheng, L., Le, Q. V., & Smola, A. J. (2009) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2009.28 · Cited by 383
Yeung, R. W., Li, S.-Y. R., Cai, N., & Zhang, Z. (2006) · Foundations and Trends® in Communications and Information Theory · doi:10.1561/0100000007 · Cited by 381
MBO: marriage in honey bees optimization-a Haplometrosis polygynous swarming approach
Abbass, H. A. (2002) · Proceedings of the 2001 Congress on Evolutionary Computation (IEEE Cat. No.01TH8546) · doi:10.1109/cec.2001.934391 · Cited by 380
A Graph-based Ant System and its convergence
Gutjahr, W. J. (2000) · Future Generation Computer Systems · doi:10.1016/s0167-739x(00)00044-3 · Cited by 368
Optimization using quantum mechanics: quantum annealing through adiabatic evolution
Santoro, G. E., & Tosatti, E. (2006) · Journal of Physics A: Mathematical and General · doi:10.1088/0305-4470/39/36/r01 · Cited by 354
Estimating Human Body Configurations Using Shape Context Matching
Mori, G., & Malik, J. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-47977-5_44 · Cited by 353
Online recognition of chinese characters: the state-of-the-art
Liu, C.-L., Jaeger, S., & Nakagawa, M. (2004) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2004.1262182 · Cited by 351
The container shipping network design problem with empty container repositioning
Shintani, K., Imai, A., Nishimura, E., & Papadimitriou, S. (2007) · Transportation Research Part E: Logistics and Transportation Review · doi:10.1016/j.tre.2005.05.003 · Cited by 349
Cell population tracking and lineage construction with spatiotemporal context
Li, K., Miller, E. D., Chen, M., Kanade, T., Weiss, L. E., & Campbell, P. G. (2008) · Medical Image Analysis · doi:10.1016/j.media.2008.06.001 · Cited by 346
Monte Carlo analysis of inverse problems
Mosegaard, K., & Sambridge, M. (2002) · Inverse Problems · doi:10.1088/0266-5611/18/3/201 · Cited by 341
An Introduction to Variable Neighborhood Search
Hansen, P., & Mladenović, N. (1999) · Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization · doi:10.1007/978-1-4615-5775-3_30 · Cited by 340
Bi, S., Huang, L., & Zhang, Y.-J. A. (2020) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2020.2988386 · Cited by 340
Models and solution techniques for frequency assignment problems
Aardal, K. I., van Hoesel, S. P. M., Koster, A. M. C. A., Mannino, C., & Sassano, A. (2007) · Annals of Operations Research · doi:10.1007/s10479-007-0178-0 · Cited by 339
Chapter 3 Stochastic and dynamic networks and routing
Powell, W. B., Jaillet, P., & Odoni, A. (1995) · Handbooks in Operations Research and Management Science · doi:10.1016/s0927-0507(05)80107-0 · Cited by 334
Peng, M., Zhang, K., Jiang, J., Wang, J., & Wang, W. (2015) · IEEE Transactions on Vehicular Technology · doi:10.1109/tvt.2014.2379922 · Cited by 333
A Characterization of Optimal Designs for Observational Studies
Rosenbaum, P. R. (1991) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.2517-6161.1991.tb01848.x · Cited by 330
A new approach to the maximum flow problem
Goldberg, A. V., & Tarjan, R. E. (1986) · Proceedings of the eighteenth annual ACM symposium on Theory of computing - STOC '86 · doi:10.1145/12130.12144 · Cited by 329
Computational complexity of μ calculation
Braatz, R. P., Young, P. M., Doyle, J. C., & Morari, M. (1994) · IEEE Transactions on Automatic Control · doi:10.1109/9.284879 · Cited by 329
Computational complexity of optimum multiuser detection
Verdú, S. (1989) · Algorithmica · doi:10.1007/bf01553893 · Cited by 325
Bioinspired computation in combinatorial optimization: algorithms and their computational complexity
Neumann, F., & Witt, C. (2012) · Proceedings of the 14th annual conference companion on Genetic and evolutionary computation · doi:10.1145/2330784.2330928 · Cited by 319
Learning object identification rules for information integration
Tejada, S., Knoblock, C. A., & Minton, S. (2001) · Information Systems · doi:10.1016/s0306-4379(01)00042-4 · Cited by 310
The complexity of facets (and some facets of complexity)
Papadimitriou, C. H., & Yannakakis, M. (1984) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(84)90068-0 · Cited by 307
Self-citation
Metadata
- Authors
- Johnson, D. S., Papadimitriou, C. H., & Steiglitz, K.
- Venue
- The American Mathematical Monthly
- Publisher
- JSTOR
- Published
- 1984-03
- Volume
- 91
- Issue
- 3
- Pages
- 209
- ISSN
- 0002-9890 (ISSN-L)
- OpenAlex
- W2053913299
- Cited by
- 5,942
- References
- 0
- FWCI
- 63.72
- Type
- journal article
- Language
- en
- Open access
- closed
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.