Approximation Algorithm for the Partial Set Multi-Cover Problem

Partial set cover problem and set multi-cover problem are two generalizations of set cover problem. In this paper, we consider the partial set multi-cover problem which is a combination of them: given an element set E, a collection of sets mathcal Ssubseteq 2E, a total covering ratio q which is a constant between 0 and 1, each set S∈mathcal S is associated with a cost cS, each element e∈ E is associated with a covering requirement re, the goal is to find a minimum cost sub-collection mathcal S'subseteqmathcal S to fully cover at least q|E| elements, where element e is fully covered if it belongs to at least re sets of mathcal S'. Denote by rmax=maxrecolon e∈ E the maximum covering requirement. We present an (O(fracrmaxlog2nvarepsilon),1-varepsilon)-bicriteria approximation algorithm, that is, the output of our algorithm has cost at most O(fracrmaxlog2 nvarepsilon) times of the optimal value while the number of fully covered elements is at least (1-varepsilon)q|E|.