On the hardness of approximating minimum vertex cover

• Autores: Samuel Safra, Irit Dinur
• Localización: Annals of mathematics, ISSN 0003-486X, Vol. 162, Nº 1, 2005, págs. 439-485
• Idioma: inglés
• DOI: 10.4007/annals.2005.162.439
• Texto completo no disponible (Saber más ...)
• Resumen

  • 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.