The value of strong inapproximability results for clique

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The value of strong inapproximability results for clique

Full text

Pdf (1.00 MB)

Source

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

Portland, Oregon, United States

Pages: 144 - 152

Year of Publication: 2000

ISBN:1-58113-184-4

Author

Aravind Srinivasan

Bell Laboratories, Lucent Technologies, 600-700 Mountain Avenue, Murray Hill, NJ

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 32, Citation Count: 1

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/335305.335322 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	Avrim Louis Blum, Algorithms for approximate graph coloring, Massachusetts Institute of Technology, Cambridge, MA, 1992
	2	Ravi Boppana , Magnús M. Halldórsson, Approximating maximum independent sets by excluding subgraphs, BIT, v.32 n.2, p.180-196, 1992 [doi>10.1007/BF01994876]
	3	L. Engebretsen and j. Holmerin. Clique is hard to approximate within n1-~(I). Manuscript, 1999.
	4	Uriel Feige, Randomized graph products, chromatic numbers, and Lovasz j-function, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.635-640, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225281]
	5	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 [doi>10.1145/226643.226652]
	6	M. M. Hallddrsson. Approximation via partitioning. Res. Report IS-RR-95-OO3F, Japan Advanced Institute of Science and Technology, 1995.
	7	Magnús M. Halldórsson, Approximations of Independent Sets in Graphs, Proceedings of the International Workshop on Approximation Algorithms for Combinatorial Optimization, p.1-13, July 18-19, 1998
	8	J. Hastad, Clique is hard to approximate within n1-, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.627, October 14-16, 1996
	9	Prabhakar Raghavan, Probabilistic construction of deterministic algorithms: approximating packing integer programs, Journal of Computer and System Sciences, v.37 n.2, p.130-143, October 1988 [doi>10.1016/0022-0000(88)90003-7]
	10	Alex Samorodnitsky , Luca Trevisan, A PCP characterization of NP with optimal amortized query complexity, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.191-199, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335329]
	11	Jeanette P. Schmidt , Alan Siegel , Aravind Srinivasan, Chernoff-Hoeffding Bounds for Applications with Limited Independence, SIAM Journal on Discrete Mathematics, v.8 n.2, p.223-250, May 1995 [doi>10.1137/S089548019223872X]
	12	Aravind Srinivasan, Improved Approximation Guarantees for Packing and Covering Integer Programs, SIAM Journal on Computing, v.29 n.2, p.648-670, Oct. 1999 [doi>10.1137/S0097539796314240]
	13	A. C.-C. Yao. Probabilistic computations: towards a unified measure of complexity. In Proc. IEEE Symposium on Foundations of Computer Science, pages 222- 227, 1977.