Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

1 Answer

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|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
add comment

Your Answer

 
discard

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.