Vertex Cover Might be Hard to Approximate to within 2-\varepsilon

Aarhus, Denmark July 07-July 10

DOI Bookmark:

http://doi.ieeecomputersociety.org/10.1109/CCC.2003.1214437

18th Annual IEEE Conference on Comput ...

	This Article
	PURCHASE ARTICLE: $19 PDF HTML IEEE Xplore Subscribers
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Subhash Khot Articles by Oded Regev

	ASCII Text	x
	Subhash Khot, Oded Regev, "Vertex Cover Might be Hard to Approximate to within 2-\varepsilon," Computational Complexity, Annual IEEE Conference on, pp. 379, 18th Annual IEEE Conference on Computational Complexity (CCC'03), 2003.

	BibTex	x
	@article{ 10.1109/CCC.2003.1214437, author = {Subhash Khot and Oded Regev}, title = {Vertex Cover Might be Hard to Approximate to within 2-\varepsilon}, journal ={Computational Complexity, Annual IEEE Conference on}, volume = {0}, year = {2003}, issn = {1093-0159}, pages = {379}, doi = {http://doi.ieeecomputersociety.org/10.1109/CCC.2003.1214437}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Computational Complexity, Annual IEEE Conference on TI - Vertex Cover Might be Hard to Approximate to within 2-\varepsilon SN - 1093-0159 SP EP A1 - Subhash Khot, A1 - Oded Regev, PY - 2003 KW - null VL - 0 JA - Computational Complexity, Annual IEEE Conference on ER -

Subhash Khot, Princeton University

Oded Regev, Institute for Advanced Study

Based on a conjecture regarding the power of unique 2-prover-1-round games presented in [15], we show that vertex cover is hard to approximate within any constant factor better than 2. We actually show a stronger result, namely, based on the same conjecture, vertex cover on k-uniform hypergraphs is hard to approximate within any constant factor better than k.

Citation:

Subhash Khot, Oded Regev, "Vertex Cover Might be Hard to Approximate to within 2-\varepsilon," ccc, pp.379, 18th Annual IEEE Conference on Computational Complexity (CCC'03), 2003

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.