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 of subsets of U, a weight function c : , a connected graph on vertex set , and a positive integer , the goal is to find a minimum weight subcollection such that the subgraph of G induced by is connected, , and the weight of is minimum. If the graph has the property that any two sets with a common element has hop distance at most r in , then the problem is called r-hop PCSC. We presented an -approximation algorithm for the minimum weight 1-hop PCSC problem and an -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.