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.

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
Mots-clés : 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://www.numdam.org/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://www.numdam.org/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://www.numdam.org/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. http://www.numdam.org/articles/10.1051/ro/2017085/

[1] A.A. Ageev and M. Sviridenko, Approximation algorithms for maximum coverage and max cut with given sizes of parts, in Proc. Conference on Integer Programming and Combinatorial Optimization, IPCO’99, edited by G. Cornuéjols, R.E. Burkard and G.J. Woeginger. Vol. 1610 of Lecture Notes in Computer Science. Springer-Verlag (1999) 17–30. | MR | Zbl

[2] N. Apollonio and B. Simeone, The maximum vertex coverage problem on bipartite graphs. Discrete Appl. Math. 165 (2014) 37–48. | DOI | MR | Zbl

[3] A. Badanidiyuru, R. Kleinberg and H. Lee, Approximating low-dimensional coverage problems, in Proc. Symposuim on Computational Geometry, SoCG’12, edited by T.K. Dey and S. Whitesides. ACM, Chapel Hill, NC (2012) 161–170. | MR | Zbl

[4] B. Caskurlu, V. Mkrtchyan, O. Parekh and K. Subramani, On partial vertex cover and budgeted maximum coverage problems in bipartite graphs, in Proc. Theoretical Computer Science, IFIP TC 1/WG 2.2 International Conference, TCS’14, edited by J. Diaz, I. Lanese and D. Sangiorgi. Vol. 8705 of Lecture Notes in Computer Science. Springer-Verlag (2014) 13–26. | MR | Zbl

[5] G. Cornuejols, M.L. Fisher and G.L. Nemhauser, Location of bank accounts to optimize float: an analytic study of exact and approximate algorithms. Manag. Sci. 23 (1977) 789–810. | DOI | MR | Zbl

[6] D.S. Hochbaum and A. Pathria, Analysis of the greedy approach in problems of maximum k-coverage. Naval Res. Logist. 45 (1998) 615–627. | DOI | MR | Zbl

[7] E. Petrank, The hardness of approximation: gap location. Comput. Complex. 4 (1994) 133–157. | DOI | MR | Zbl

[8] L. Trevisan, Max cut and the smallest eigenvalue, in Proc. STOC’09 (2009) 263–272. | Zbl

Cité par Sources :