Title :
Vertex cover might be hard to approximate to within 2-ϵ
Author :
Khot, Subhash ; Regev, Oded
Author_Institution :
Dept. of Comput. Sci., Princeton Univ., NJ, USA
Abstract :
Based on a conjecture regarding the power of unique 2-prover-1-round games presented in [S. Khot, (2002)], 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.
Keywords :
approximation theory; computational complexity; game theory; graph theory; probability; set theory; theorem proving; 2-prover-1-round game; NP-hard problem; constant factor approximation; k-uniform hypergraph; vertex cover hardness; Approximation algorithms; Artificial intelligence; Bismuth; Computational complexity; Linear programming;
Conference_Titel :
Computational Complexity, 2003. Proceedings. 18th IEEE Annual Conference on
Print_ISBN :
0-7695-1879-6
DOI :
10.1109/CCC.2003.1214437
