Vertex cover might be hard to approximate to within 2-/spl epsiv/
By Subhash Khot, Oded Regev. 18th IEEE Annual Conference on Computational Complexity, 2003. Proceedings., 2003
637 citations recorded by the source corpus.
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.
Subfields: Computational Theory and Mathematics, Computer Networks and Communications
View Paper: https://www.semanticscholar.org/paper/57f50af031548a69a0738a2059e5fb2956d670c2
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Theory and Mathematics
In Computer Networks and Communications
Citations in the corpus
- Towards Sharp Inapproximability For Any 2-CSP (2007, neutral): “Examples of such results include 2 − hardness for VERTEX COVER [24], superconstant hardness for SPARSESTCUT [10, 25] and MULTICUT [10], hardness of approximating M AX INDEPENDENTSET within d/poly(log d) in degreed graphs [31], and approximation resistance 2 for random predicates [19].”
- Noise Stability of Functions with Low Influences: Invariance and Optimality II - The Non Reversible Case (2007, background): “There are by now quite a few results in hardness of approximation that use results on low-influence functions or require conjectured such results; e.g., [8] [15] [6] [18] [16].”