0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Is this a home work question? If not, what is the motivation or context? $\endgroup$ – Chandra Chekuri Oct 21 '18 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 Oct 21 '18 at 18:47
0
$\begingroup$

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.

$\endgroup$
  • 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$ – Chandra Chekuri Oct 21 '18 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 Oct 21 '18 at 18:58
  • 1
    $\begingroup$ @Labo first chapter of Williamson and Shmoys $\endgroup$ – Sasho Nikolov Oct 22 '18 at 1:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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