The maximum (unweighted) coverage problem is defined as follows:
- 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.
This problem is NP-hard. I am trying to find a counterexample when the greedy algorithm fails but I failed. Especially, can you find a family of instances when the greedy algorithm always fails? (Or at least one simple instance?)
- The greedy algorithm: at each stage, choose a set which contains the largest number of uncovered elements.
I found a family of instances here but it was for the weighted case and I cannot transform it to the unweighted case.