Tight instance for unweighted maximum coverage problem?

Question

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.

Answer 1

Here is one example: take the universe $$U=\{u_1,\dots,u_n,v_1,\dots,v_n\}$$ $S_i=\{u_i,v_i\}$ for $i=1,\dots,n$ , and $S_{n+1}=\{u_1,\dots,u_n\}$, $m=n+1$, $k=n$