Approximation algorithm for the partial set multi-cover problem

Partial set cover problem and set multi-cover problem are two generalizations of the 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$$S⊆2E, a total covering ratio q, each set $$S\in \mathcal S$$S∈S is associated with a cost $$c_S$$cS, each element $$e\in E$$e∈E is associated with a covering requirement $$r_e$$re, the goal is to find a minimum cost sub-collection $${\mathcal {S}}'\subseteq {\mathcal {S}}$$S′⊆S to fully cover at least q|E| elements, where element e is fully covered if it belongs to at least $$r_e$$re sets of $${\mathcal {S}}'$$S′. Denote by $$r_{\max }=\max \{r_e:e\in E\}$$rmax=max{re:e∈E} the maximum covering requirement. We present an $$(O (r_{\max }\log ^2n(1+\ln (\frac{1}{\varepsilon })+\frac{1-q}{\varepsilon q})),1-\varepsilon )$$(O(rmaxlog2n(1+ln(1ε)+1-qεq)),1-ε)-bicriteria approximation algorithm, that is, the output of our algorithm has cost $$O(r_{\max }\log ^2 n(1+\ln (\frac{1}{\varepsilon })+\frac{1-q}{\varepsilon q}))$$O(rmaxlog2n(1+ln(1ε)+1-qεq)) times of the optimal value while the number of fully covered elements is at least $$(1-\varepsilon )q|E|$$(1-ε)q|E|.