no. 1
Combinatorial approximation of maximum k-vertex cover in bipartite graphs within ratioย 0.7
RAIRO. Operations Research, Volume 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
Keywords: Approximation algorithm, bipartite graph, max k-VERTEX cover 
@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},
     pages = {305--314},
     year = {2018},
     publisher = {EDP-Sciences},
     volume = {52},
     number = {1},
     doi = {10.1051/ro/2017085},
     zbl = {1401.05238},
     mrnumber = {3812482},
     language = {en},
     url = {https://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
PY  - 2018
SP  - 305
EP  - 314
VL  - 52
IS  - 1
PB  - EDP-Sciences
UR  - https://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
%D 2018
%P 305-314
%V 52
%N 1
%I EDP-Sciences
%U https://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, Volume 52 (2018) no. 1, pp. 305-314. doi: 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. | Zbl | MR

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

[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. | Zbl | MR

[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. | Zbl | MR

[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. | Zbl | MR | DOI

[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. | Zbl | MR | DOI

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

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

Cited by Sources: