Quantifiers and approximation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Quantifiers and approximation

Full text

Pdf (754 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-second annual ACM symposium on Theory of computing table of contents

Baltimore, Maryland, United States

Pages: 446 - 456

Year of Publication: 1990

ISBN:0-89791-361-2

Authors

A. Panconesi	Department of Computer Science, Cornell University, Ithaca, NY
D. Ranjan	Department of Computer Science, Cornell University, Ithaca, NY

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 19, Citation Count: 7

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/100216.100275 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	[1] G. Ausiello, A. Marchetti Spaccamela and M. Protasi "Toward a unified approach for the classification of NP-complete problems" Theory Comput Sci, 12 (1980), 83-96.
	2	[2] D. Bruschi, D. Joseph and P. Young "A structural Overview of NP Optimization Problems" Comp Sci Tech Report 861, Univ of Wisconsin-Madison (1989).
	3	Pierluigi Crescenzi , Alessandro Panconesi, Completeness in Approximation Classes, Proceedings of the International Conference on Fundamentals of Computation Theory, p.116-126, August 21-25, 1989
	4	[4] R. Fagin "Generalized First-Order Spectra, and Polynomial-Time Recognizable Sets" in Complexity and Computations, R. Karp editor, AMS, (1974).
	5	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	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	Dorit S. Hochbaum , David B. Shmoys, Using dual approximation algorithms for scheduling problems theoretical and practical results, Journal of the ACM (JACM), v.34 n.1, p.144-162, Jan. 1987 [doi>10.1145/7531.7535]
	8	[8] D. Johnson "Approximation algorithms for combinatorial problems" J Computer and System Sci, 9 (1974), 256-278.
	9	Mark W. Krentel, The complexity of optimization problems, Journal of Computer and System Sciences, v.36 n.3, p.490-509, June 1988 [doi>10.1016/0022-0000(88)90039-6]
	10	[10] P. Orponen and H. Mannila "On approximation preserving reductions: complete problems and robust measures" Tech Report, University of Helsinki 1987.
	11	[11] A. Paz and S. Moran "NP-optimization problems and their approximation" Theory Comput Sci, 15 (1981), 251-277.
	12	Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
	13	Christos Papadimitriou , Mihalis Yannakakis, Optimization, approximation, and complexity classes, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.229-234, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62233]

CITED BY 7

	Sanjeev Arora, The approximability of NP-hard problems, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.337-348, May 24-26, 1998, Dallas, Texas, United States
	Sanjeev Khanna , Rajeev Motwani, Towards a syntactic characterization of PTAS, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.329-337, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Uriel Feige , Shafi Goldwasser , Laszlo Lovász , Shmuel Safra , Mario Szegedy, Interactive proofs and the hardness of approximating cliques, Journal of the ACM (JACM), v.43 n.2, p.268-292, March 1996
	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
	Leonard Pitt , Manfred K. Warmuth, The minimum consistent DFA problem cannot be approximated within any polynomial, Journal of the ACM (JACM), v.40 n.1, p.95-142, Jan. 1993
	Laurent Alfandari , Vangelis Th. Paschos, Master-Slave Strategy and Polynomial Approximation, Computational Optimization and Applications, v.16 n.3, p.231-245, Sept. 2000
	Patrik Floréen , Pekka Orponen, Attraction radii in binary hopfield nets are hard to compute, Neural Computation, v.5 n.5, p.812-821, September 1993