Approximating Max-Coverage when the elements need to be covered multiple times

Question

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!

Answer 1

If the required number of times we need to cover an element is 2, we have the following densest k-subgraph problem: (Imagine the edges are elements and nodes are sets.)

Given a graph $G$ and an integer $k$, find a subgraph of $G$ on $k$ nodes with maximum density.

Khot proved that no PTAS exists under plausible complexity assumptions; there is an $O(n^{1/4+\epsilon})$ approximation to the problem by Bhaskara, Charikar, Chlamtac, Feige and Vijayaraghavan; a polynomial integrality gaps result by Bhaskara, Charikar, Guruswami, Vijayaraghavan and Zhou. Therefore I believe your question is hard to approximate in the most general case.