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{S}\subseteq 2^E$, a total covering ratio $q$ which is a constant between 0 and 1, each set $S\in \mathcal{S}$ is associated with a cost $c_S$, each element $e\in E$ is associated with a covering requirement $r_e$, the goal is to find a minimum cost sub-collection $\mathcal S’\subseteq\mathcal S$tofullycoveratleast$q|E|$elements,whereelement$e$ is fully covered if it belongs to at least $r_e$ sets of ${\mathcal{S}}^{\mathrm{\prime }}$. Denote by $r_{\max }=\max \{r_e\text{\hspace{0.17em}⁣}:e\in E\}$ the maximum covering requirement. We present an $(O(\frac{r_{\max }{\log }^{2}n}{\epsilon }),1-\epsilon )$-bicriteria approximation algorithm, that is, the output of our algorithm has cost at most $O(\frac{r_{\max }{\log }^{2}n}{\epsilon })$ times of the optimal value while the number of fully covered elements is at least $(1-\epsilon )q\mathrm{\mid }E\mathrm{\mid }$.