### Abstract

This paper studies approximation algorithm for the maximum weight budgeted connected set cover (MWBCSC) problem. Given an element set , a collection of sets , a weight function on , a cost function on , a connected graph (called communication graph) on vertex set , and a budget , the MWBCSC problem is to select a subcollection such that the cost , the subgraph of induced by is connected, and the total weight of elements covered by (that is ) is maximized. We present a polynomial time algorithm for this problem with a natural communication graph that has performance ratio , where is the maximum degree of graph and is the number of sets in . In particular, if every set has cost at most , the performance ratio can be improved to .

Original language | English |
---|---|

Pages (from-to) | 1505-1517 |

Number of pages | 13 |

Journal | Journal of Combinatorial Optimization |

Volume | 31 |

Issue number | 4 |

DOIs | |

State | Published - May 2016 |

### Keywords

- Budgeted set cover; Connected set cover; Approximation algorithm

## Fingerprint Dive into the research topics of 'An approximation algorithm for maximum weight budgeted connected set cover'. Together they form a unique fingerprint.

## Cite this

Ran, Y., Zhao, Z., Ko, K-I., & Liang, J. (2016). An approximation algorithm for maximum weight budgeted connected set cover.

*Journal of Combinatorial Optimization*,*31*(4), 1505-1517. https://doi.org/10.1007/s10878-015-9838-1