An Overview of Complexity Theory in Discrete Optimization: Part II. Results and Implications
- 1 June 1982
- journal article
- research article
- Published by Taylor & Francis in A I I E Transactions
- Vol. 14 (2) , 83-89
- https://doi.org/10.1080/05695558208975042
Abstract
Over the past decade, complexity theory has emerged from a branch of computer science almost unknown in the operations research community into a topic of widespread interest and research. Part I of this tutorial overview of the subject (TRANSACTIONS, March 1982) developed important background concepts of the theory. This paper uses that background to define and investigate the implications of NP-Hardness, NP-Completeness, NP-Equivalency, the NP≠NP conjecture, and various approximations.Keywords
This publication has 8 references indexed in Scilit:
- An Overview of Complexity Theory in Discrete Optimizations: Part I. ConceptsIIE Transactions, 1982
- Combinatorial Optimization: What is the State of the ArtMathematics of Operations Research, 1980
- A Patching Algorithm for the Nonsymmetric Traveling-Salesman ProblemSIAM Journal on Computing, 1979
- Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the PlaneMathematics of Operations Research, 1977
- Fast Approximation Algorithms for the Knapsack and Sum of Subset ProblemsJournal of the ACM, 1975
- Approximate Algorithms for the 0/1 Knapsack ProblemJournal of the ACM, 1975
- The complexity of theorem-proving proceduresPublished by Association for Computing Machinery (ACM) ,1971
- Optimal two‐ and three‐stage production schedules with setup times includedNaval Research Logistics Quarterly, 1954