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

	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	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

18th Annual IEEE Conference on Computational Complexity (CCC'03)

Aarhus, Denmark

July 07-July 10

ISBN: 0-7695-1879-6

	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

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

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.