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\), a collection of sets \({\mathcal {S}}\subseteq 2^X\), a weight function \(w\) on \(X\), a cost function \(c\) on \({\mathcal {S}}\), a connected graph \(G_{\mathcal {S}}\) (called communication graph) on vertex set \({\mathcal {S}}\), and a budget \(L\), the MWBCSC problem is to select a subcollection \({\mathcal {S'}}\subseteq {\mathcal {S}}\) such that the cost \(c({\mathcal {S'}})=\sum _{S\in {\mathcal {S'}}}c(S)\le L\), the subgraph of \(G_{\mathcal {S}}\) induced by \({\mathcal {S'}}\) is connected, and the total weight of elements covered by \({\mathcal {S'}}\) (that is \(\sum _{x\in \bigcup _{S\in {\mathcal {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)\), where \(\delta \) is the maximum degree of graph \(G_{\mathcal {S}}\) and \(n\) is the number of sets in \({\mathcal {S}}\). In particular, if every set has cost at most \(L/2\), the performance ratio can be improved to \(O(\log n)\).