Sartaj Sahni
Teofilo Gonzalez
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.
- 1 BODIN, L D. A graph theoretic approach to the grouping of ordering data. Networks 2 (1972), 307- 310Google Scholar
- 2 BRUNO, J, COFFMAN, E G, AND SETm, R Scheduling independent tasks to reduce mean finishrag-time Comm ACM 17, 7 (July 1974), 382-387. Google Scholar
- 3 CONWAY, R W., MAXWELL, N.L, AND MILLER, L W Theory of Scheduhng Addison-Wesley, Reading, Mass, 1967Google Scholar
- 4 CooK, S A The complexity of theorem-proving procedures Conf. Record of Third ACM Syrup on Theory of Computing, 1970, pp 151-158. Google Scholar
- 5 GARFINKEL, R S., AND NEMHAUSER, G L Integer Programming Wiley, New York, 1972Google Scholar
- 6 GARE~, M R, AND JOHNSON, D S The complexity of near-optimal graph coloring. J ACM 23, 1 (Jan 1976), 43-69 Google Scholar
- 7 GAREY, M R, JOHNSON, D S, AND STOCKMEYER, L J Some simplified NP-complete problems Theoretical Comput Sc~ (to appear) Google Scholar
- 8 GRAHAM, R L Bounds on multlprocesslng timing anomalies SIAM j Appl Math 17, 2 (March 1969), 416-429Google Scholar
- 9 HOROWITZ, E, AND SAHNI, S Exact and approximate algorithms for scheduhng nomdentlcal processors J ACM 23, 2 (April 1976), 317-327 Google Scholar
- 10 InAaRA, O H, AND KIM, C E Fast approximation algorithms for the knapsack and sum of subset problems. J ACM 22, 4 (Oct. 1975), 463-468. Google Scholar
- 11 JOHNSON, D Approximation algorithms for combinatorml problems. J Comput. Syst Sczs 9, 3 (Dec 1974), 256-278Google Scholar
- 12 JOHNSON, D.B, ANY LAFUENTF., J M A controlled single pass classification algorithm with{ application to multilevel clustering Scientific Rep #ISR-18, Information Sczence and Retrieval, Cornell U , Ithaca, N Y , Oct 1970, pp XII-1-XII-37Google Scholar
- 13 KARP, R M Reducibility among combinatorial problems In Complexity of Computer Computa-{ tions, R E Miller and J W Thatcher, Eds , Plenum Press, N Y, 1972, pp 85-104Google Scholar
- 14 KNUTH, D E. A terminological proposal ACM SIGACT News 6, 1 (Jan 1974), 12-18Google Scholar
- 15 LUKES, J A Combinatorml solutmn to the partitioning of general graphs IBM J Res and Develop 19, 2 (March 1975), 170-180Google Scholar
- 16 ROS~NKRASTZ, D J , STEAar~S, R E , ANn L~.wm, P M Approximate algorithms for the travelhng salesperson problem 15th Annual IEEE Symp on Switching and Automata Theory, 1974, pp 33- 42Google Scholar
- 17 Ross, G T, AND SOLAND, R M A branch and bound algorithm for the generalized assignment problem Math Programming 8 (1975), 91-103Google Scholar
- 18 SAHNI, S. Algorithms for scheduhng independent tasks J ACM 23, 1 (Jan 1976), 116-127 Google Scholar
- 19 SAHNI, S Computationally related problems. SIAM J Comput 3, 4 (Dec 1974), pp 262-279Google Scholar
- 20 SAHNI, S Approximate algorithms for the 0/1 knapsack problem J ACM22, 1 (Jan 1975), 115- 124 Google Scholar
Index Terms
- P-Complete Approximation Problems
Recommendations
Approximation of Natural W[P]-Complete Minimisation Problems Is Hard
CCC '08: Proceedings of the 2008 IEEE 23rd Annual Conference on Computational ComplexityWe prove that the weighted monotone circuit satisfiability problem has no fixed-parameter tractable approximation algorithm with constant or polylogarithmic approximation ratio unless FPT = W[P]. Our result answers a question of Alekhnovich and Razborov,...
Optimal Approximation Algorithms for Maximum Distance-Bounded Subgraph Problems
In this paper we study the (in)approximability of two distance-based relaxed variants of the maximum clique problem (Max Clique), named Max d-Clique and Max d-Club: A d-clique in a graph $$G = (V, E)$$G=(V,E) is a subset $$S\subseteq V$$S⊆V of vertices ...
Comments