摘要 : 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 version o... 展开 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 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. 收起