Local ratio method on partial set multi-cover

In this paper, we study the minimum partial set multi-cover problem (PSMC). Given an element set E, a collection of subsets $${\mathcal {S}}\subseteq 2^E$$ S ⊆ 2 E , a cost $$c_S$$ c S on each set $$S\in {\mathcal {S}}$$ S ∈ S , a covering requirement $$r_e$$ r e for each element $$e\in E$$ e ∈ E , and an integer k, the PSMC problem is to find a sub-collection $${\mathcal {F}}\subseteq {\mathcal {S}}$$ F ⊆ S to fully cover at least k elements such that the cost of $${\mathcal {F}}$$ F is as small as possible, where element e is fully covered by $${\mathcal {F}}$$ F if it belongs to at least $$r_e$$ r e sets of $${\mathcal {F}}$$ F . This paper presents an approximation algorithm using local ratio method achieving performance ratio $$\max \left\{ \frac{\Delta }{k}\left( \frac{1}{f-r_{\min }}+\frac{r_{\max }}{r_{\min }}\right) ,\frac{1}{\rho }+\frac{f}{r_{\min }}+\frac{1}{r_{\max }}-\frac{1}{\rho r_{\max }}-1,\frac{1}{\rho }\right\} $$ max Δ k 1 f - r min + r max r min , 1 ρ + f r min + 1 r max - 1 ρ r max - 1 , 1 ρ , where $$\Delta $$ Δ is the size of a maximum set, f is the maximum number of sets containing a common element, $$\rho $$ ρ is the minimum percentage of elements required to be fully covered during iterations of the algorithm, and $$r_{\max }$$ r max and $$r_{\min }$$ r min are the maximum and the minimum covering requirement, respectively. In particular, when $$r_{\max }$$ r max is a constant, the first term can be omitted. Notice that our ratio coincides with the classic ratio f for both the set multi-cover problem (in which case $$k=|E|$$ k = | E | ) and the partial set single-cover problem (in which case $$r_{\max }=1$$ r max = 1 ). However, when $$k 1$$ r max > 1 , the ratio might be as large as $$\Theta (n)$$ Θ ( n ) . This result shows an interesting “shock wave like” feature of approximating PSMC. The purpose of this paper is trying to arouse some interest in such a feature and attract more work on this challenging problem.