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 U, a collection \({\mathcal {S}}\) of subsets function c : {S}} \rightarrow {\mathbb {Q}}^{+}\), graph \(G_{{\mathcal {S}}}\) on vertex {S}}\), and positive integer \(k\le |U|\), goal is to find subcollection {S}}' \subseteq {\mathcal such that subgraph G induced by {S}}'\) connected, \(|\bigcup _{S\in {S}}^{\prime }}S| \ge k\), minimum. If has property any two sets with common hop distance at most r in {S}}}\), then called r-hop PCSC. We presented \(O(\ln (m+n))\)-approximation algorithm for 1-hop PCSC cardinality problem. Our performance ratio improves previous results our method much simpler than methods.