Randomized graph products, chromatic numbers, and Lovasz j-function

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Randomized graph products, chromatic numbers, and Lovasz j-function

Full text

Pdf (562 KB)

Source

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

Las Vegas, Nevada, United States

Pages: 635 - 640

Year of Publication: 1995

ISBN:0-89791-718-9

Author

Uriel Feige

Department of Applied Math and Computer Science, The Weizmann Institute, Rehovot 76100, Israel

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): 26, Citation Count: 6

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/225058.225281 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	N. Alon, N. Kahale. "Approximating the inde-pendence number via the 0-function". Manuscript, November 1994.
	2	S. Arora, C. Lund, R. Motwani, M. Sudan, M. Szegedy. "Proof verification and hardness of ap-proximation problems". 33rd FOCS, 14-23, 1992.
	3	S. Arora, S. Safra. "Probabilistic checking of proofs: a new characterization of NP". 33rd FOG'S, 2-13, 1992.
	4	Mihir Bellare , Madhu Sudan, Improved non-approximability results, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.184-193, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195129]
	5	Piotr Berman , Georg Schnitger, On the complexity of approximating the independent set problem, Information and Computation, v.96 n.1, p.77-94, Jan. 1992 [doi>10.1016/0890-5401(92)90056-L]
	6	Avrim Louis Blum, Algorithms for approximate graph coloring, Massachusetts Institute of Technology, Cambridge, MA, 1992
	7	Avrim Blum, New approximation algorithms for graph coloring, Journal of the ACM (JACM), v.41 n.3, p.470-516, May 1994 [doi>10.1145/176584.176586]
	8	R. Boppana , M. M. Halldórsson, Approximating maximum independent sets by excluding subgraphs, Proceedings of the second Scandinavian workshop on Algorithm theory, p.13-25, July 1990, Bergen, Sweden
	9	U. Feige , S. Goldwasser , L. Lovász , S. Safra , M. Szegedy, Approximating clique is almost NP-complete (preliminary version), Proceedings of the 32nd annual symposium on Foundations of computer science, p.2-12, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185341]
	10	P. Frankl, R, Wilson. "Intersection theorems with geometric consequences". Cornbinatorica 1, 357- 368, 1981.
	11	Michel X. Goemans , David P. Williamson, .879-approximation algorithms for MAX CUT and MAX 2SAT, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.422-431, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195216]
	12	M. Grotschel, L. Lovasz, A. Schrijver. "Geomet-ric algorithms and combinatorial optimization". Springer- Verlag, Berlin, 1987.
	13	W. Hoeffding. "Probability inequalities for sums bounded random variables". Journal of the Amer-zcan Statistical Assoczatton, 58 (1963) 13-30.
	14	D. Karger, R. Motwani, M. Sudan. "Approximate Graph Coloring by Semidefinite Programming". 35th FOCS, 2-13, 1994.
	15	D. Knuth. "The sandwich theorem". The elec-tronic journal of combinatorzcsl 1:1-48, 1994.
	16	N. Linial, U. Vazirani. "Graph products and chro-matic numbers". 30th FOCS, 124-1.28, 1989.
	17	L. Lovasz. "On the ratio of the optimal integral and fractional covers". Discrete Mathematics 13 (1975) 383-390.
	18	L. Lovasz. "On the Shannon Capacity of a Graph". IEEE Trans. on Information Theory, Vol. IT-25, No. 1, pp. 1-7, 1979.
	19	Carsten Lund , Mihalis Yannakakis, On the hardness of approximating minimization problems, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.286-293, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167172]
	20	M. Szegedy. '(A note on the $ number of Lovasz and the generalized Delsart,e bound". 35th FOCS, 36-39, 1994.
	21	Avi Wigderson, Improving the performance guarantee for approximate graph coloring, Journal of the ACM (JACM), v.30 n.4, p.729-735, Oct. 1983 [doi>10.1145/2157.2158]

CITED BY 6

	Aravind Srinivasan, The value of strong inapproximability results for clique, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.144-152, May 21-23, 2000, Portland, Oregon, United States
	Johan Håstad, Testing of the long code and hardness for clique, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.11-19, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	David Karger , Rajeev Motwani , Madhu Sudan, Approximate graph coloring by semidefinite programming, Journal of the ACM (JACM), v.45 n.2, p.246-265, March 1998
	Vangelis T. Paschos, A survey of approximately optimal solutions to some covering and packing problems, ACM Computing Surveys (CSUR), v.29 n.2, p.171-209, June 1997
	Valentin Brimkov, Algorithmic and explicit determination of the Lovász number for certain circulant graphs, Discrete Applied Mathematics, v.155 n.14, p.1812-1825, September, 2007
	Misha Alekhnovich , Mark Braverman , Vitaly Feldman , Adam R. Klivans , Toniann Pitassi, The complexity of properly learning simple concept classes, Journal of Computer and System Sciences, v.74 n.1, p.16-34, February, 2008