Optimization, approximation, and complexity classes
Christos H. Papadimitriou, Mihalis Yannakakis · Journal of Computer and System Sciences · 1991
Cited by 1,653 works. doi:10.1016/0022-0000(91)90023-x
Authors
References
- Computers and Intractability: A Guide to the Theory of NP-Completeness
- Reducibility among Combinatorial Problems
- The complexity of theorem-proving procedures
- Complexity of Computer Computations
- Approximation algorithms for combinatorial problems
- The Complexity of Near-Optimal Graph Coloring
- Planar 3-colorability is polynomial complete
- Generalized first-order spectra and polynomial-time recognizable sets
- The Traveling Salesman Problem with Distances One and Two
- Some Examples of Difficult Traveling Salesman Problems