Combinatorial approximation of maximum k-vertex cover in bipartite graphs within ratio 0.7
Vangélis Th. Paschos · RAIRO - Operations Research · 2017
We propose and analyze a simple purely combinatorial algorithm 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.