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 _{Sin {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 _{xin bigcup _{Sin {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)).