Lesson plan
Maximum coverage problem
The maximum coverage problem is a classical question in computer science, computational complexity theory, and operations research. It is a problem that is widely taught in approximation algorithms. As input you are given several sets and a number k . The sets may have some elements in common. You must select at most k of these sets such that the maximum number of elements are covered, i.e. the union of the selected sets has maximal size. Formally, (unweighted) Maximum Coverage : Instance: A number k and a collection of sets S = \{S_1, S_2, \ldots, S_m\} . : Objective: Find a subset S' \subseteq S of sets, such that \left| S' \right| \leq k and the number of covered elements \left| \bigcup_{S_i \in S'}{S_i} \right| is maximized. The maximum coverage problem is NP-hard, and cannot be approximated to within 1 - \frac{1}{e} + o(1) \approx 0.632 under standard assumptions. This result essentially matches the approximation ratio achieved by the generic greedy algorithm used for maximization of submodular functions with a cardinality constraint.
Article summary
The maximum coverage problem is a classical question in computer science, computational complexity theory, and operations research. It is a problem that is widely taught in approximation algorithms. As input you are given several sets and a number k . The sets may have some elements in common. You must select at most k of these sets such that the maximum number of elements are covered, i.e. the union of the selected sets has maximal size. Formally, (unweighted) Maximum Coverage : Instance: A number k and a collection of sets S = \{S_1, S_2, \ldots, S_m\} . : Objective: Find a subset S' \subseteq S of sets, such that \left| S' \right| \leq k and the number of covered elements \left| \bigcup_{S_i \in S'}{S_i} \right| is maximized. The maximum coverage problem is NP-hard, and cannot be approximated to within 1 - \frac{1}{e} + o(1) \approx 0.632 under standard assumptions. This result essentially matches the approximation ratio achieved by the generic greedy algorithm used for maximization of submodular functions with a cardinality constraint.
Key claims
No claims recorded.
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
No sources recorded.
Key claims and bibliography are generated from the same tracked claims and sources as the article page.