%0 Journal Article
%T A 0.821-ratio purely combinatorial algorithm for maximum $k$-vertex cover in bipartite graphs
%A Edouard Bonnet
%A Bruno Escoffier
%A Vangelis Paschos
%A Georgios Stamoulis
%J Computer Science
%D 2014
%I arXiv
%X Our goal in this paper is to propose a \textit{combinatorial algorithm} that beats the only such algorithm known previously, the greedy one. We study the polynomial approximation of the Maximum Vertex Cover Problem in bipartite graphs by a purely combinatorial algorithm and present a computer assisted analysis of it, that finds the worst case approximation guarantee that is bounded below by~0.821.
%U http://arxiv.org/abs/1409.6952v2