An approximation algorithm for maximum weight budgeted connected set cover

This paper studies approximation algorithm for the maximum weight budgeted connected set cover (MWBCSC) problem. Given an element set $$X$$ X , a collection of sets $${\mathcal {S}}\subseteq 2^X$$ S ⊆ 2 X , a weight function $$w$$ w on $$X$$ X , a cost function $$c$$ c on $${\mathcal {S}}$$ S , a connected graph $$G_{\mathcal {S}}$$ G S (called communication graph) on vertex set $${\mathcal {S}}$$ S , and a budget $$L$$ L , the MWBCSC problem is to select a subcollection $${\mathcal {S'}}\subseteq {\mathcal {S}}$$ S ′ ⊆ S such that the cost $$c({\mathcal {S'}})=\sum _{S\in {\mathcal {S'}}}c(S)\le L$$ c ( S ′ ) = ∑ S ∈ S ′ c ( S ) ≤ L , the subgraph of $$G_{\mathcal {S}}$$ G S induced by $${\mathcal {S'}}$$ S ′ is connected, and the total weight of elements covered by $${\mathcal {S'}}$$ S ′ (that is $$\sum _{x\in \bigcup _{S\in {\mathcal {S'}}}S}w(x)$$ ∑ x ∈ ⋃ S ∈ S ′ S w ( x ) ) is maximized. We present a polynomial time algorithm for this problem with a natural communication graph that has performance ratio $$O((\delta +1)\log n)$$ O ( ( δ + 1 ) log n ) , where $$\delta $$ δ is the maximum degree of graph $$G_{\mathcal {S}}$$ G S and $$n$$ n is the number of sets in $${\mathcal {S}}$$ S . In particular, if every set has cost at most $$L/2$$ L / 2 , the performance ratio can be improved to $$O(\log n)$$ O ( log n ) .