TY - JOUR
T1 - Vertex cover might be hard to approximate to within 2 - ε
AU - Khot, Subhash
AU - Regev, Oded
N1 - Funding Information:
* Corresponding author. E-mail address: [email protected] (S. Khot). 1 Supported by Prof. Sanjeev Arora’s David and Lucile Packard Fellowship, NSF Grant CCR-0098180, and an NSF ITR grant. 2 Supported by an Alon Fellowship, by the Binational Science Foundation, by the Israel Science Foundation, and by the Project QAP.
PY - 2008/5
Y1 - 2008/5
N2 - Based on a conjecture regarding the power of unique 2-prover-1-round games presented in [S. Khot, On the power of unique 2-Prover 1-Round games, in: Proc. 34th ACM Symp. on Theory of Computing, STOC, May 2002, pp. 767-775], 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.
AB - Based on a conjecture regarding the power of unique 2-prover-1-round games presented in [S. Khot, On the power of unique 2-Prover 1-Round games, in: Proc. 34th ACM Symp. on Theory of Computing, STOC, May 2002, pp. 767-775], 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.
KW - Hardness of approximation
KW - Unique games conjecture
KW - Vertex cover
UR - http://www.scopus.com/inward/record.url?scp=38149105774&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=38149105774&partnerID=8YFLogxK
U2 - 10.1016/j.jcss.2007.06.019
DO - 10.1016/j.jcss.2007.06.019
M3 - Article
AN - SCOPUS:38149105774
SN - 0022-0000
VL - 74
SP - 335
EP - 349
JO - Journal of Computer and System Sciences
JF - Journal of Computer and System Sciences
IS - 3
ER -