On approximation of the submodular set cover problem

We design a primal–dual heuristic for the submodular set cover problem and analyze its performance giving an approximation bound as a generalization of the one for the set cover problem. As an application, a capacitated version of the partial vertex cover problem on hypergraphs with edge size at most d is considered. It will be shown that the problem can be approximated in polynomial time within a factor of d of the optimum, generalizing some existing results.