A primal-dual algorithm for the minimum partial set multi-cover problem

In a minimum partial set multi-cover problem (MinPSMC), given an element set E, a collection of subsets S subset of 2E a cost wSon each set S is an element of S a covering requirement re\for each element e is an element of Eand an integer k, the goal is to find a sub-collection F subset of S to fully cover at least k elements such that the cost of F is as small as possible, where element e is fully covered by F if it belongs to at least re sets of FOn the application side, the problem has its background in the seed selection problem in a social network. On the theoretical side, it is a natural combination of the minimum partial (single) set cover problem (MinPSC) and the minimum set multi-cover problem (MinSMC). Although both MinPSC and MinSMC admit good approximations whose performance ratios match those lower bounds for the classic set cover problem, previous studies show that theoretical study on MinPSMC is quite challenging. In this paper, we prove that MinPSMC cannot be approximated within factor O(n12(loglogn)c)for some constant c under the ETH assumption. Furthermore, assuming rmax is a constant, where rmax=maxe is an element of Ere is the maximum covering requirement and f is the maximum number of sets containing a common element, we present a primal-dual algorithm for MinPSMC and show that its performance ratio is O(n) We also improve the ratio for a restricted version of MinPSMC which possesses a graph-type structure.