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].