Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 0 down vote accepted

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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