Geodesic
On the hardness of approximating vertex cover
Irit Dinur1 ; Samuel Safra2
1 The Selim and Rachel Benin School of Computer Science and Engineering, The Hebrew University of Jerusalem, 91904 Jerusalem, Israel
2 School of Computer Sciences, Tel Aviv University, 69978 Tel Aviv, Israel
Annals of mathematics, Tome 162 (2005) no. 1, pp. 439-485.

Voir la notice de l'article provenant de la source Annals of Mathematics website

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.
DOI : 10.4007/annals.2005.162.439

Irit Dinur 1 ; Samuel Safra 2

1 The Selim and Rachel Benin School of Computer Science and Engineering, The Hebrew University of Jerusalem, 91904 Jerusalem, Israel
2 School of Computer Sciences, Tel Aviv University, 69978 Tel Aviv, Israel 
@article{10_4007_annals_2005_162_439,
     author = {Irit Dinur and Samuel Safra},
     title = {On the hardness of approximating vertex cover},
     journal = {Annals of mathematics},
     pages = {439--485},
     publisher = {mathdoc},
     volume = {162},
     number = {1},
     year = {2005},
     doi = {10.4007/annals.2005.162.439},
     mrnumber = {2178966},
     zbl = {1084.68051},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.4007/annals.2005.162.439/}
}
TY  - JOUR
AU  - Irit Dinur
AU  - Samuel Safra
TI  - On the hardness of approximating vertex cover
JO  - Annals of mathematics
PY  - 2005
SP  - 439
EP  - 485
VL  - 162
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.4007/annals.2005.162.439/
DO  - 10.4007/annals.2005.162.439
LA  - en
ID  - 10_4007_annals_2005_162_439
ER  - 
%0 Journal Article
%A Irit Dinur
%A Samuel Safra
%T On the hardness of approximating vertex cover
%J Annals of mathematics
%D 2005
%P 439-485
%V 162
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.4007/annals.2005.162.439/
%R 10.4007/annals.2005.162.439
%G en
%F 10_4007_annals_2005_162_439
Irit Dinur; Samuel Safra. On the hardness of approximating vertex cover. Annals of mathematics, Tome 162 (2005) no. 1, pp. 439-485. doi : 10.4007/annals.2005.162.439. http://geodesic.mathdoc.fr/articles/10.4007/annals.2005.162.439/

Cité par Sources :