In the set multicover problem we are given a set N of n elements and a set S of m subsets of N. Additionally, each element has a coverage requirement, i.e. the number of times it has to be covered. The question is to cover N with the minimum number of subsets from S. I'm aware of the approximation algorithms for this problem (Rajagopalan & Vazirani).
I'm interested in a different version of the problem (max multi-coverage). We are given K and we ask for the maximal number of the elements from N we can cover with K subsets from S. We count an element as covered if it is covered at least the required number of times. Are there any approximation algorithms for this case? Are there any lower bounds for this case (or even for the standard set multicover problem)?
Thanks in advance!