On approximation of the submodular set cover problem

We design a primal-dural 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 vers ion of the partial vertex cover problem on hypergraphs with edge size at mo st d is considered. It will be shown that the problem can be approximated i n polynomial time within a factor of d of the optimum, generalizing some ex isting results. (C) 1999 Elsevier Science B.V. All rights reserved.