Geodesic
Combinatorial approximation of maximum k-vertex cover in bipartite graphs within ratio 0.7
RAIRO - Operations Research - Recherche Opérationnelle, Tome 52 (2018) no. 1, pp. 305-314

Voir la notice de l'article provenant de la source Numdam

We propose and analyze a simple 𝑝𝑢𝑟𝑒𝑙𝑦 𝑐𝑜𝑚𝑏𝑖𝑛𝑎𝑡𝑜𝑟𝑖𝑎𝑙 𝑎𝑙𝑔𝑜𝑟𝑖𝑡ℎ𝑚 for MAX k - VERTEX COVER in bipartite graphs, achieving approximation ratio 0.7. The only combinatorial algorithm currently known until now for this problem is the natural greedy algorithm, that achieves ratio ( e - 1 ) e = 0.632.

DOI : 10.1051/ro/2017085
Classification : 03D15, 05C70, 05C85, 68Q25, 68W25, 68W40
Keywords: Approximation algorithm, bipartite graph, max k-VERTEX cover

Paschos, Vangelis Th. 1

1 
@article{RO_2018__52_1_305_0,
     author = {Paschos, Vangelis Th.},
     title = {Combinatorial approximation of maximum k-vertex cover in bipartite graphs within ratio~0.7},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {305--314},
     publisher = {EDP-Sciences},
     volume = {52},
     number = {1},
     year = {2018},
     doi = {10.1051/ro/2017085},
     zbl = {1401.05238},
     mrnumber = {3812482},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ro/2017085/}
}
TY  - JOUR
AU  - Paschos, Vangelis Th.
TI  - Combinatorial approximation of maximum k-vertex cover in bipartite graphs within ratio 0.7
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2018
SP  - 305
EP  - 314
VL  - 52
IS  - 1
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ro/2017085/
DO  - 10.1051/ro/2017085
LA  - en
ID  - RO_2018__52_1_305_0
ER  - 
%0 Journal Article
%A Paschos, Vangelis Th.
%T Combinatorial approximation of maximum k-vertex cover in bipartite graphs within ratio 0.7
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2018
%P 305-314
%V 52
%N 1
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ro/2017085/
%R 10.1051/ro/2017085
%G en
%F RO_2018__52_1_305_0
Paschos, Vangelis Th. Combinatorial approximation of maximum k-vertex cover in bipartite graphs within ratio 0.7. RAIRO - Operations Research - Recherche Opérationnelle, Tome 52 (2018) no. 1, pp. 305-314. doi: 10.1051/ro/2017085

Cité par Sources :