<p>I ended up finding the answer.</p>

<p>I'm going to prove the greedy algorithm yields the correct answer.</p>

<p>Count the number of membership relationships. There are at least <span class="math-container">$n\cdot k$</span>, so one set must contain more than <span class="math-container">$\frac{n\cdot k}m$</span> elements.</p>

<p>After one step of greedy algorithm, there are less than <span class="math-container">$n_1 = n - \frac{n\cdot k}m = n \left(1 - \frac km\right)$</span> elements left.</p>

<p>At the second step we remove at least <span class="math-container">$n_1(1-\frac{k}{m-1})$</span>.</p>

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

<p>Since <span class="math-container">$\log(1-x) &lt; -x$</span>, <span class="math-container">$\log(n) &lt; \sum_{i=0}^j \frac{k}{m-i}$</span> is sufficient.</p>

<p>We are looking for the smallest <span class="math-container">$j$</span> such that:</p>

<p><span class="math-container">$ m-j &lt; \exp(\log(m) - \frac{\log(n)}{k}) = \frac{m}{n^\frac1k}$</span></p>

<p><span class="math-container">$\Longleftrightarrow j &gt; m\left(1-\frac{1}{n^\frac1k}\right) = m\left(1-\frac{1}{\exp(\frac{log(n)}{k}}\right)$</span></p>

<p>Now, <span class="math-container">$1-\frac{1}{\exp(x)} ≤ x$</span> by convexity, hence <span class="math-container">$j &gt; \frac{m \log(n)}{k}$</span> is sufficient.</p>

CC BY-SA 4.0
2018-10-21T18:51:01.013Z
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.
Chandra Chekuri
CC BY-SA 4.0
2018-10-21T18:58:40.050Z
@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
CC BY-SA 4.0
2018-10-22T01:32:02.497Z
@Labo first chapter of Williamson and Shmoys
Sasho Nikolov
CC BY-SA 4.0
2018-10-21T18:46:27.230Z
2018-10-21T18:46:27.230Z
Labo
<p>We want to cover <span class="math-container">$n$</span> elements with some sets from <span class="math-container">$S_1, …, S_m$</span> (classical set cover).</p>

<p>We furthermore suppose that any element belongs to at least <span class="math-container">$k$</span> sets and want to find a set cover with cardinal at most <span class="math-container">$\mathcal{O}\left(\frac{m \cdot log(n)}{k}\right)$</span>.</p>

<p>For <span class="math-container">$k=1$</span>, the classical greedy algorithm works, but after that I'm stuck.</p>

CC BY-SA 4.0
2018-10-21T17:51:35.597Z
Is this a home work question? If not, what is the motivation or context?
Chandra Chekuri
CC BY-SA 4.0
2018-10-21T18:47:58.300Z
@ChandraChekuri It is an exercise I found interesting. I spent 1 hour yesterday trying randomized algorithms, but the greedy worked at the end.
Labo
<approximation-algorithms><set-cover>
Polynomial approximation algorithm for set cover with assumption
Labo
# Polynomial approximation algorithm for set cover with assumption

(Asked by: username_0 on 2018-10-21)

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.

**Tags:** approximation-algorithms, set-cover

> **Comments:**
> **username_1**: Is this a home work question? If not, what is the motivation or context?  
> **username_0**: @ChandraChekuri It is an exercise I found interesting. I spent 1 hour yesterday trying randomized algorithms, but the greedy worked at the end.  

---

## 1 answers

### Answer by username_0 on 2018-10-21. Score: 0 | Accepted answer

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.

> **Comments:**
> **username_1**: 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.  
> **username_0**: @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?  
> **username_2**: @username_0 first chapter of Williamson and Shmoys  

---

