P-Complete Approximation Problems
- 1 July 1976
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 23 (3), 555-565
- https://doi.org/10.1145/321958.321975
Abstract
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.Keywords
This publication has 12 references indexed in Scilit:
- Exact and Approximate Algorithms for Scheduling Nonidentical ProcessorsJournal of the ACM, 1976
- The Complexity of Near-Optimal Graph ColoringJournal of the ACM, 1976
- Algorithms for Scheduling Independent TasksJournal of the ACM, 1976
- A branch and bound algorithm for the generalized assignment problemMathematical Programming, 1975
- Fast Approximation Algorithms for the Knapsack and Sum of Subset ProblemsJournal of the ACM, 1975
- Combinatorial Solution to the Partitioning of General GraphsIBM Journal of Research and Development, 1975
- Approximate algorithms for the traveling salesperson problemPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1974
- Scheduling independent tasks to reduce mean finishing timeCommunications of the ACM, 1974
- Reducibility among Combinatorial ProblemsPublished by Springer Science and Business Media LLC ,1972
- A graph theoretic approach to the grouping of ordering dataNetworks, 1972