# 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?

-

## 1 Answer

Yes. The above problem can be reduced to a generalization of the Maximum Coverage Problem, called Budgeted 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.

See the wiki page and reference within. Hope it helps.

-
This seems right. I am not sure about C(Si)=|Si|. The same elements can be on different sets, so the cost varies. – manix Nov 28 '12 at 23:25