Abstract
We prove the Minimum Vertex Cover problem to be NP-hard to approximate to within a factor of $1.3606$, extending on previous PCP and hardness of approximation technique. To that end, one needs to develop a new proof framework, and to borrow and extend ideas from several fields.
Full Article