Pages 439-485 from Volume 162 (2005), Issue 1 by Irit Dinur, Samuel Safra
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.
Received: 7 October 2002
Revised: 26 May 2004
Accepted: 12 June 2003
Published online: 1 March 2009
The Selim and Rachel Benin School of Computer Science and Engineering, The Hebrew University of Jerusalem, 91904 Jerusalem, Israel
School of Computer Sciences, Tel Aviv University, 69978 Tel Aviv, Israel