IMPROVED APPROXIMATION OF MAXIMUM VERTEX COVERAGE PROBLEM ON BIPARTITE GRAPHS

Given a simple undirected graph G and a positive integer s, the maximum vertex coverage problem (MVC) is the problem of finding a set U of s vertices of G such that the number of edges having at least one endpoint in U is as large as possible. The problem is NP-hard even in bipartite graphs, as shown in two recent papers [N. Apollonio and B. Simeone, Discrete Appl. Math., 165 (2014), pp. 37-48; G. Joret and A. Vetta, Reducing the Rank of a Matroid, preprint, arXiv: 1211.4853v1 [cs.DS], 2012]. By exploiting the structure of the fractional optimal solutions of a linear programming formulation for the maximum coverage problem, we provide a 4/5-approximation algorithm for the problem. The algorithm immediately extends to the weighted version of MVC.