A note on the Clustered Set Covering Problem

We define an NP  -hard clustered variant of the Set Covering Problem where subsets are partitioned into KK clusters and a fixed cost is paid for selecting at least one subset in a given cluster. We show that the problem is approximable within ratio (1+ϵ)(e/e−1)H(q)(1+ϵ)(e/e−1)H(q), where qq is the maximum number of elements covered by a cluster and H(q)=∑i=1q1i.