A simple approximation algorithm for minimum weight partial connected set cover

This paper studies the minimum weight partial connected set cover problem (PCSC). Given an element set U, a collection $${\mathcal {S}}$$ S of subsets of U, a weight function c : $${\mathcal {S}} \rightarrow {\mathbb {Q}}^{+}$$ S → Q + , a connected graph $$G_{{\mathcal {S}}}$$ G S on vertex set $${\mathcal {S}}$$ S , and a positive integer $$k\le |U|$$ k ≤ | U | , the goal is to find a minimum weight subcollection $${\mathcal {S}}' \subseteq {\mathcal {S}}$$ S ′ ⊆ S such that the subgraph of G induced by $${\mathcal {S}}'$$ S ′ is connected, $$|\bigcup _{S\in {\mathcal {S}}^{\prime }}S| \ge k$$ | ⋃ S ∈ S ′ S | ≥ k , and the weight of $${\mathcal {S}}'$$ S ′ is minimum. If the graph $$G_{{\mathcal {S}}}$$ G S has the property that any two sets with a common element has hop distance at most r in $$G_{{\mathcal {S}}}$$ G S , then the problem is called r-hop PCSC. We presented an $$O(\ln (m+n))$$ O ( ln ( m + n ) ) -approximation algorithm for the minimum weight 1-hop PCSC problem and an $$O(\ln (m+n))$$ O ( ln ( m + n ) ) -approximation algorithm for the minimum cardinality r-hop PCSC problem. Our performance ratio improves previous results and our method is much simpler than previous methods.