2004 | OriginalPaper | Buchkapitel
Maximum Coverage Problem with Group Budget Constraints and Applications
verfasst von : Chandra Chekuri, Amit Kumar
Erschienen in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 ${\cal S} = \{S_1, S_2, \ldots, S_m\}$ 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 ${\cal S}$ to maximize the cardinality of their union. In the MCG problem ${\cal S}$ is partitioned into groupsG1, G2, ..., Gℓ. The goal is to pick k sets from ${\cal 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.