P-Complete Approximation Problems

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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	BODIN, L D. A graph theoretic approach to the grouping of ordering data. Networks 2 (1972), 307- 310
	2	J. Bruno , E. G. Coffman, Jr. , R. Sethi, Scheduling independent tasks to reduce mean finishing time, Communications of the ACM, v.17 n.7, p.382-387, July 1974 [doi>10.1145/361011.361064]
	3	CONWAY, R W., MAXWELL, N.L, AND MILLER, L W Theory of Scheduhng Addison-Wesley, Reading, Mass, 1967
	4	Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
	5	GARFINKEL, R S., AND NEMHAUSER, G L Integer Programming Wiley, New York, 1972
	6	M. R. Garey , D. S. Johnson, The Complexity of Near-Optimal Graph Coloring, Journal of the ACM (JACM), v.23 n.1, p.43-49, Jan. 1976 [doi>10.1145/321921.321926]
	7	M. R. Garey , D. S. Johnson , L. Stockmeyer, Some simplified NP-complete problems, Proceedings of the sixth annual ACM symposium on Theory of computing, p.47-63, April 30-May 02, 1974, Seattle, Washington, United States [doi>10.1145/800119.803884]
	8	GRAHAM, R L Bounds on multlprocesslng timing anomalies SIAM j Appl Math 17, 2 (March 1969), 416-429
	9	Ellis Horowitz , Sartaj Sahni, Exact and Approximate Algorithms for Scheduling Nonidentical Processors, Journal of the ACM (JACM), v.23 n.2, p.317-327, April 1976 [doi>10.1145/321941.321951]
	10	Oscar H. Ibarra , Chul E. Kim, Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems, Journal of the ACM (JACM), v.22 n.4, p.463-468, Oct. 1975 [doi>10.1145/321906.321909]
	11	JOHNSON, D Approximation algorithms for combinatorml problems. J Comput. Syst Sczs 9, 3 (Dec 1974), 256-278
	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-37
	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-104
	14	KNUTH, D E. A terminological proposal ACM SIGACT News 6, 1 (Jan 1974), 12-18
	15	LUKES, J A Combinatorml solutmn to the partitioning of general graphs IBM J Res and Develop 19, 2 (March 1975), 170-180
	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- 42
	17	Ross, G T, AND SOLAND, R M A branch and bound algorithm for the generalized assignment problem Math Programming 8 (1975), 91-103
	18	Sartaj K. Sahni, Algorithms for Scheduling Independent Tasks, Journal of the ACM (JACM), v.23 n.1, p.116-127, Jan. 1976 [doi>10.1145/321921.321934]
	19	SAHNI, S Computationally related problems. SIAM J Comput 3, 4 (Dec 1974), pp 262-279
	20	Sartaj Sahni, Approximate Algorithms for the 0/1 Knapsack Problem, Journal of the ACM (JACM), v.22 n.1, p.115-124, Jan. 1975 [doi>10.1145/321864.321873]