On the hardness of approximating minimum vertex cover

• 成果类型: Article
• 署名作者: Dinur, I; Safra, S
• 刊物名称: ANNALS OF MATHEMATICS
• ISSN/ISSBN: 0003-486X
• DOI: 10.4007/annals.2005.162.439
• 发表日期: 2005
• 页码: 439-485
• 关键词: zero-one law; finite sets; algorithms; threshold; systems; THEOREM; proofs; np

摘要

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.