Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR01-104 | 17th December 2001 00:00

The Importance of Being Biased

RSS-Feed




TR01-104
Authors: Irit Dinur, Shmuel Safra
Publication: 23rd December 2001 13:10
Downloads: 1480
Keywords: 


Abstract:

We show Minimum Vertex Cover NP-hard to approximate to within a factor
of 1.3606. This improves on the previously known factor of 7/6.



ISSN 1433-8092 | Imprint