@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",

}