P-Complete Approximation Problems
Sartaj K. Sahni, Teofilo F. Gonzalez · Journal of the ACM · 1976
For P-complete problems such as traveling salesperson, cycle covers, 0-1 integer programming, multicommodity network flows, quadratic assignment, etc., it is shown that the approximation problem is also P-complete. In contrast with these results, a linear time approximation algorithm for the clustering problem is presented.
Cited by 1,703 works. doi:10.1145/321958.321975 Open-access PDF
Authors
References
- Reducibility among Combinatorial Problems
- The complexity of theorem-proving procedures
- Approximation algorithms for combinatorial problems
- Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
- Approximating Complex Surfaces by Triangulation of Contour Lines
- The Complexity of Near-Optimal Graph Coloring
- Some simplified NP-complete problems
- Algorithms for Scheduling Independent Tasks
- Approximate Algorithms for the 0/1 Knapsack Problem
- Scheduling independent tasks to reduce mean finishing time