Purely combinatorial approximation algorithms for maximum k-vertex cover in bipartite graphs

We study the polynomial time approximation of the NP-hard maxk-vertex cover problem in bipartite graphs and propose purely combinatorial approximation algorithms. The main result of the paper is a simple combinatorial algorithm and a computer-assisted analysis of its approximation guarantee giving strong evidence that the worst approximation ratio achieved is bounded below by 0.821. We also study two simpler strategies with provable approximation ratios of 23 and 3447≈0.72 respectively that already beat the only such known algorithm, namely the greedy approach which guarantees ratio (1−1e)≈0.632. Our principal motivation is to bring a satisfactory answer in the following question: to what extent combinatorial methods for maxk-vertex cover compete with linear programming ones?