# Proof of NP-completness for the foll0wing

I have encountered a problem similar to Set Cover (and Maximum Coverage):

We have several sets in a universe with $N$ elements. What is the maximum number of sets so that the number of elements found in these sets is not greater than $\frac{N}{2}$.

Can this problem be reduced to Set Cover or Maximum Coverage?

-

Using the terminology of wiki page, select the weight of each object $e_j =1$ and cost $C(S_i) = |S_i|$, the size of $S_i$. Select the budget to be $\frac{N}{2}$. Then your problem is exactly equal to solving the given problem.