Chekuri, Chandra ; Kumar, Amit
(2004)
*Maximum Coverage Problem with Group Budget Constraints and Applications*
Lecture Notes in Computer Science, 3122
.
pp. 72-83.
ISSN 0302-9743

Full text not available from this repository.

Official URL: http://doi.org/10.1007/978-3-540-27821-4_7

Related URL: http://dx.doi.org/10.1007/978-3-540-27821-4_7

## Abstract

We study a variant of the maximum coverage problem which we label the maximum coverage problem with group budget constraints (MCG). We are given a collection of sets S={S1,S2,…,Sm} where each set S i is a subset of a given ground set X. In the maximum coverage problem the goal is to pick k sets from S to maximize the cardinality of their union. In the MCG problem S is partitioned into groupsG 1, G 2, ..., G ℓ. The goal is to pick k sets from S to maximize the cardinality of their union but with the additional restriction that at most one set be picked from each group. We motivate the study of MCG by pointing out a variety of applications. We show that the greedy algorithm gives a 2-approximation algorithm for this problem which is tight in the oracle model. We also obtain a constant factor approximation algorithm for the cost version of the problem. We then use MCG to obtain the first constant factor approximation algorithms for the following problems: (i) multiple depot k-traveling repairmen problem with covering constraints and (ii) orienteering problem with time windows when the number of time windows is a constant.

Item Type: | Article |
---|---|

Source: | Copyright of this article belongs to Springer-Verlag. |

ID Code: | 123552 |

Deposited On: | 30 Sep 2021 10:28 |

Last Modified: | 30 Sep 2021 10:28 |

Repository Staff Only: item control page