@inbook{7a6ab597d7e94250878f488d476e56e2,
title = "Maximum coverage problem with group budget constraints and applications",
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 Si 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 groups G1, G2, . . . , 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.",
author = "Chandra Chekuri and Amit Kumar",
year = "2004",
doi = "10.1007/978-3-540-27821-4_7",
language = "English (US)",
isbn = "3540228942",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer",
pages = "72--83",
editor = "Klaus Jansen and Sanjeev Khanna and Rolim, {Jose D. P.} and Dana Ron",
booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
address = "Germany",
}