| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 429892 | Journal of Computer and System Sciences | 2008 | 15 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
