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.

• Is this a home work question? If not, what is the motivation or context? Oct 21 '18 at 17:51
• @ChandraChekuri It is an exercise I found interesting. I spent 1 hour yesterday trying randomized algorithms, but the greedy worked at the end.
– Labo
Oct 21 '18 at 18:47

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) < 1$$, ie $$\log(n) + \sum_{i=0}^j \log\left(1-\frac{k}{m-i}\right) < 0$$.

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

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

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

$$\Longleftrightarrow j > 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 > \frac{m \log(n)}{k}$$ is sufficient.

• Since you found the answer here is another way to do it via the well-known LP relaxation for Set Cover. Since each element is in at least k sets one can find a feasible fractional solution of value at most $m/k$ by choosing each set to an extent of $1/k$. Then another standard result is that Greedy gives a solution of cost at most $OPT_{LP} H_p$ where $OPT_{LP}$ is the value of the optimum LP solution and $H_p$ is the $p$'th harmonic number where $p$ is the maximum set size. Since $p \le n$ and we have seen that $OPT_{LP} \le m/k$ the result follows. Oct 21 '18 at 18:51
• @ChandraChekuri Thank you very much. "Then another standard result is that Greedy gives a solution of cost at most $OPT_{LP}H_p$" do you have a source / name?
– Labo
Oct 21 '18 at 18:58
• @Labo first chapter of Williamson and Shmoys Oct 22 '18 at 1:32