LAUSR

In a minimum partial set multi-cover problem (MinPSMC), given an element set X , a collection of subsets $${\mathcal {S}} \subseteq 2^X$$ S ⊆ 2 X , a cost $$c_S$$ c S on each set $$S\in {\mathcal {S}}$$ S ∈ S , a covering requirement $$r_x$$ r x for each element $$x\in X$$ x ∈ X , and an integer k , the goal 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 x is fully covered by $${\mathcal {F}}$$ F if it belongs to at least $$r_x$$ r x sets of $${\mathcal {F}}$$ F . Recently, it was proved that MinPSMC is at least as hard as the densest k -subgraph problem. The question is: how about the problem in some geometric settings? In this paper, we consider the MinPSMC problem in which X is a set of points on the plane and $${\mathcal {S}}$$ S is a set of unit squares (MinPSMC-US). Under the assumption that $$r_x=f_x$$ r x = f x for every $$x\in X$$ x ∈ X , where $$f_x=|\{S\in {\mathcal {S}}:x\in S\}|$$ f x = | { S ∈ S : x ∈ S } | is the number of sets containing element x , we design an approximation algorithm achieving approximation ratio $$(1+\varepsilon )$$ ( 1 + ε ) for MinPSMC-US.