Optimization, approximation, and complexity classes
- 2 December 1991
- journal article
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 43 (3) , 425-440
- https://doi.org/10.1016/0022-0000(91)90023-x
Abstract
No abstract availableKeywords
This publication has 16 references indexed in Scilit:
- Approximation algorithms for combinatorial problemsPublished by Elsevier ,2007
- On the complexity of approximating the independent set problemInformation and Computation, 1992
- The complexity of optimization problemsJournal of Computer and System Sciences, 1988
- How well can a graph be n-colored?Discrete Mathematics, 1981
- Non deterministic polynomial optimization problems and their approximationsTheoretical Computer Science, 1981
- Toward a unified approach for the classification of NP-complete optimization problemsTheoretical Computer Science, 1980
- Structure preserving reductions among convex optimization problemsJournal of Computer and System Sciences, 1980
- On the structure of combinatorial problems and structure preserving reductionsPublished by Springer Nature ,1977
- The Complexity of Near-Optimal Graph ColoringJournal of the ACM, 1976
- Planar 3-colorability is polynomial completeACM SIGACT News, 1973