1
$\begingroup$

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 Answers 1

0

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.

  • 0
    This seems right. I am not sure about C(Si)=|Si|. The same elements can be on different sets, so the cost varies.2012-11-28