Complexity of Partial Satisfaction

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Complexity of Partial Satisfaction

Full text

Pdf (674 KB)

Source

Journal of the ACM (JACM) archive
Volume 28 , Issue 2 (April 1981) table of contents

Pages: 411 - 421

Year of Publication: 1981

ISSN:0004-5411

Authors

K. J. Lieberherr	Department of Electrical Engineering and Computer Science, Princeton University, Princeton, NJ and Swiss Federal Institute of Technology, Zurich, Switzerland
E. Specker	Department of Mathematics, Swiss Federal Institute of Technology, ETH Zurich, Ch-8092 Zurich, Switzerland

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 39, Citation Count: 9

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/322248.322260 What is a DOI?

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	CARMICHAEL, R.D.Introduction to the Theory of Groups of Finite Order. Dover, New York, 1937.
	2	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]
	3	ERDOS, P, AND KLEITMAN, D J On colormg graphs to maximize the proportion of mulacolored K- edges. J Comb Theory 5, 2 (1968), 164-169
	4	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]
	5	GAREY, M R, AND JOHNSON, D.S.Approximation algorithms for combinatorial problems--an annotated bibliography. In Algorithms and Complexity. Recent Results and New Directions, J Traub, Ed., Academic Press, New York, 1976, 41-52
	6	GAREY, M R, AND JOHNSON, D.S Computers and lntractabthty. Freeman, San Francisco, 1979
	7	JOHNSON, D S.Approximation algorithms for combinatorial problems j Comput Syst. Scl 9 (1974), 256-278.
	8	KARP, R.M.Reduclblhty among combinatorial problems In Complexuy of Computer Computatlons, R E. Miller and J W. Thatcher, Eds, Plenum Press, New York, 1972, pp 85-104.
	9	LANDAU, E.Handbuch der Lehre yon der Vertedung der Prtmzahlen. Chelsea Publishing, New York, 1974.
	10	LIEBERHERR, K.J.Towards feasible solutions of NP-complete problems, Tech. Rep No. 14, Institute for InformaUcs, ETH Zentrum, CH-8092 Zurich, Switzerland, 1975
	11	LIEBERHERR, K J.P-opumal heurlsUcs Theoret Comput. Sct. 10, 2 (1980), 123-131.
	12	LIEBERHERR, K J.Probabihstic combinatorial optimization Tech Rep. 281, Dep of Electrical Engineering and Computer Science, Princeton Umv, Princeton, N J, 1981
	13	LIEBERHERR, K J, AND SPECKER, E interpretations of 2-satisfiable conjunctive normal forms. Not Am. Math Soc. 25, 2 (1978), A-295.
	14	LIEBERHERR, K.J, AND SPECKER, E Complexity of partial satlsfacUon. 20th Ann IEEE Symp on Foundations of Computer Science, San Juan, Puerto Rico, 1979, pp 132-139

CITED BY 9

	Mihalis Yannakakis, On the approximation of maximum satisfiability, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.1-9, September 1992, Orlando, Florida, United States
	Dorit S. Hochbaum , David B. Shmoys, A unified approach to approximation algorithms for bottleneck problems, Journal of the ACM (JACM), v.33 n.3, p.533-550, July 1986
	Takao Asano , David P. Williamson, Improved approximation algorithms for MAX SAT, Journal of Algorithms, v.42 n.1, p.173-202, January 2002
	Takao Asano , David P. Williamson, Improved approximation algorithms for MAX SAT, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.96-105, January 09-11, 2000, San Francisco, California, United States
	Endre Boros , Peter L. Hammer, Pseudo-boolean optimization, Discrete Applied Mathematics, v.123 n.1-3, p.155-225, 15 November 2002
	David J. Haglin , Shankar M. Venkatesan, Approximation and Intractability Results for the Maximum Cut Problem and Its Variants, IEEE Transactions on Computers, v.40 n.1, p.110-113, January 1991
	Daniel Král, Locally satisfiable formulas, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Zdeněk Dvořák , Daniel Král , Ondřej Pangrác, Locally consistent constraint satisfaction problems, Theoretical Computer Science, v.348 n.2, p.187-206, 8 December 2005
	N. D. Dendris , L. M. Kirousis , Y. C. Stamatiou , D. M. Thilikos, On Parallel Partial Solutions and Approximation Schemesfor Local Consistency in Networks of Constraints, Constraints, v.5 n.3, p.251-273, July 2000