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 - 2003
Y1 - 2003
N2 - The general problem of vertex cover on k-uniform hypergraphs is considered. The Ek-Vertex-Cover problem is the problem of finding a minimum size vertex cover in a k-uniform hypergraph. The hypergraph contains no independent set of size δ. It is concluded that vertex cover on k-uniform hypergraphs is hard to approximate within any constant factor better than k.
AB - The general problem of vertex cover on k-uniform hypergraphs is considered. The Ek-Vertex-Cover problem is the problem of finding a minimum size vertex cover in a k-uniform hypergraph. The hypergraph contains no independent set of size δ. It is concluded that vertex cover on k-uniform hypergraphs is hard to approximate within any constant factor better than k.
UR - http://www.scopus.com/inward/record.url?scp=0043016118&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0043016118&partnerID=8YFLogxK
M3 - Conference article
AN - SCOPUS:0043016118
SN - 1093-0159
SP - 379
EP - 386
JO - Proceedings of the Annual IEEE Conference on Computational Complexity
JF - Proceedings of the Annual IEEE Conference on Computational Complexity
T2 - 18th Annual IEEE Conference on Computational Complexity
Y2 - 7 July 2003 through 10 July 2003
ER -