A 0.821-ratio purely combinatorial algorithm for maximum $k$-vertex cover in bipartite graphs

Edouard Bonnet, Bruno Escoffier, Vangelis Paschos +1

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 o…