Maximum Coverage Problem

Given an universe $U = \{e_1, e_2, \dots, e_n\}$ of elements, a list of sets $\{Si \subseteq U \}_{i=1}^m$ (possibly overlapping) and a bound $K$, the goal is to find $K$ sets $S'_1, S'_2, \dots, S'_K$ such that $|\bigcup_{i=1}^K S'_i|$ is maximized.

This is NP-hard

NP is the set of decision problems where YES answer has proof that can be checked in polynomial time, even if finding that proof might be hard. Intuitively, NP is the set of decision problems solvable in polynomial time by a nondeterministic Turing maching, and verifiable in polynomial time by a deterministic one.

A problem $\Pi$ is NP-hard if a polynomial-time algorithm for $\Pi$ would imply a polynomial-time algorithm for every problem in NP. In other words:

$\Pi$ is NP-hard $\Longleftrightarrow$ If $\Pi$ can be solved in polynomial time, then P=NP

The Greedy Algorithm

Even though exact solutions are expensive, a simple greedy strategy gives a guaranteed approximation:

1. Start with an empty collection.
2. At each step, pick the set $S_i$ that covers the most still-uncovered elements.
3. Repeat until you have chosen $K$ sets.

Theorem (Nemhauser, Wolsey, Fisher, 1978):
The greedy algorithm achieves a $(1 - 1/e) \approx 63.2\%$ approximation ratio. This is the best possible polynomial-time guarantee unless $\mathsf{P} = \mathsf{NP}$.