Polynomial approximation algorithm for set cover with assumption We want to cover $n$ elements with some sets from $S_1, …, S_m$ (classical set cover).

We furthermore suppose that any element belongs to at least $k$ sets and want to find a set cover with cardinal at most $\mathcal{O}\left(\frac{m \cdot log(n)}{k}\right)$.

For $k=1$, the classical greedy algorithm works, but after that I'm stuck.
I ended up finding the answer.

I'm going to prove the greedy algorithm yields the correct answer.

Count the number of membership relationships. There are at least $n\cdot k$, so one set must contain more than $\frac{n\cdot k}m$ elements.

After one step of greedy algorithm, there are less than $n_1 = n - \frac{n\cdot k}m = n \left(1 - \frac km\right)$ elements left.

At the second step we remove at least $n_1(1-\frac{k}{m-1})$.

We are guaranteed to terminate when $n~\Pi_{i=0}^j \left( 1-\frac{k}{m-i}\right) &lt; 1$, ie $\log(n) + \sum_{i=0}^j \log\left(1-\frac{k}{m-i}\right) &lt; 0$.

Since $\log(1-x) &lt; -x$, $\log(n) &lt; \sum_{i=0}^j \frac{k}{m-i}$ is sufficient.

We are looking for the smallest $j$ such that:

$ m-j &lt; \exp(\log(m) - \frac{\log(n)}{k}) = \frac{m}{n^\frac1k}$

$\Longleftrightarrow j &gt; m\left(1-\frac{1}{n^\frac1k}\right) = m\left(1-\frac{1}{\exp(\frac{log(n)}{k}}\right)$

Now, $1-\frac{1}{\exp(x)} ≤ x$ by convexity, hence $j &gt; \frac{m \log(n)}{k}$ is sufficient.