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.

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

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
3
  • 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, 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
    Oct 21, 2018 at 18:58
  • 1
    $\begingroup$ @Labo first chapter of Williamson and Shmoys $\endgroup$
    – Sasho Nikolov
    Oct 22, 2018 at 1:32

Your Answer

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

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