Non deterministic polynomial optimization problems and their approximations
- 1 January 1981
- journal article
- Published by Elsevier in Theoretical Computer Science
- Vol. 15 (3) , 251-277
- https://doi.org/10.1016/0304-3975(81)90081-5
Abstract
No abstract availableKeywords
This publication has 11 references indexed in Scilit:
- General approximation algorithms for some arithmetical combinatorial problemsTheoretical Computer Science, 1981
- Combinatorial Problems: Reductibility and ApproximationOperations Research, 1978
- `` Strong '' NP-Completeness ResultsJournal of the ACM, 1978
- On the structure of combinatorial problems and structure preserving reductionsPublished by Springer Nature ,1977
- P-Complete Approximation ProblemsJournal of the ACM, 1976
- The Complexity of Near-Optimal Graph ColoringJournal of the ACM, 1976
- Fast Approximation Algorithms for the Knapsack and Sum of Subset ProblemsJournal of the ACM, 1975
- Computationally Related ProblemsSIAM Journal on Computing, 1974
- Postscript about NP-hard problemsACM SIGACT News, 1974
- Relationships between nondeterministic and deterministic tape complexitiesJournal of Computer and System Sciences, 1970