Proof of NP-completeness for the following

89 Views Asked by At

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

There are 1 best solutions below

1
On BEST 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.