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.

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

1 Answer 1


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.

  • 1
    $\begingroup$ 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. $\endgroup$ Commented Oct 21, 2018 at 18:51
  • $\begingroup$ @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? $\endgroup$
    – Labo
    Commented Oct 21, 2018 at 18:58
  • 1
    $\begingroup$ @Labo first chapter of Williamson and Shmoys $\endgroup$ Commented Oct 22, 2018 at 1:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.