1
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.