<p>Here's one randomized $O(\log n)$-approximation algorithm (not well known I'm afraid), for unit-cost set cover.</p>

<p><strong>input</strong>: collection of sets over $n$ elements, upper bound $U$ on opt</p>

<p><strong>output</strong>: w/probability $\ge 1/2$, a set cover of size $O(U \ln n)$.</p>

<ol>
<li><p>Let $K=\lceil \ln(2n)U/0.99\rceil$.  Let $T=\ln(100)$.</p></li>
<li><p>Create $K$ tokens, each with an associated unit-rate Poisson process.</p></li>
<li><p>As time $t$ increases continuously from $0$ to $T$, do the following:
When a Poisson process fires at time $t$, 
remove its token from its current set (if any), 
then place it on a set $s$ chosen to maximize
$$
\sum_{e\in s}
\Big(
\frac{1-1/U}{1/f(t) - 1/U}
\Big)^{C^{(t)}_e},
$$
where $C^{(t)}_e$ denotes the number of tokens (other than the firing token) 
currently covering element $e$, and $f(t) \doteq 1-\exp(-(T-t))$.</p></li>
<li><p>Return the sets that have tokens on them.</p></li>
</ol>

<p>When a token fires, it moves 
to a set whose elements have largest total ``weight''.
Initially, when $t\approx 0$, the weight of element $e$
is about $.99^{C_e} \approx 1$,
so the algorithm essentially moves tokens onto the largest sets.
When $t\approx T-\ln 2$, the weight of an element $e$ is about $.5^{C_e}$.
Thus, each token on a set covering $e$ cuts $e$'s weight by a factor of $1/2$.
Finally, when $t\approx T-\epsilon$, an element $e$ has weight about
$\epsilon^{C_e}$, so only uncovered (or minimally covered) elements contribute significant weight.</p>

<p>If $U$ is unknown, 
then binary search can be used 
to find the smallest integer $U$ 
between $1$ and $n$ 
for which the algorithm works.</p>

<p>Here is the approximation guarantee:</p>

<p><strong>Theorem.</strong>
<em>If there exists a fractional set cover of size $U$,
then, with probability at least 1/2,  the algorithm returns
a set cover of size at most $\lceil \ln(2n)U/0.99\rceil$.</em></p>

<p>For the derivation and proof see <a href="https://algnotes.info/on/obliv/greedy/set-cover-grasp/" rel="nofollow noreferrer">https://algnotes.info/on/obliv/greedy/set-cover-grasp/</a>.</p>

<h3>One more</h3>

<p>Oh, and there is a well-known randomized <em>parallel</em> algorithm for set cover, namely <a href="http://www.dcg.ethz.ch/lectures/ws0405/seminar/papers/primal_dual.pdf" rel="nofollow noreferrer">Primal-dual RNC approximation algorithms for set cover and covering integer programs</a> by Rajagopalan and Vazirani.</p>

CC BY-SA 3.0
2012-11-06T16:48:01.003Z
This looks like a reinterpretation of the multiplicative weight update method. Is it ?
Suresh Venkat
CC BY-SA 3.0
2012-12-08T03:12:25.987Z
No, but the underlying techniques can be used to derive both algorithms.  See [http://greedyalgs.info/blog/grasp-set-cover](http://greedyalgs.info/blog/grasp-set-cover) for the derivation (and poke around further for how the same ideas give multiplicative weights update algorithms).
Neal Young
CC BY-SA 3.0
2017-07-12T01:23:19.117Z
Since solving the LP  approximately via multiplicative weight updates is essentially the same time as the above algorithm, I wonder if it wouldn't be better to solve the LP first and then do randomized rounding. This way, one also gets a lower bound on the optimum value and which can be used to judge the quality of the approximate solution.
Chandra Chekuri
CC BY-SA 4.0
2023-01-12T22:26:19.737Z
Yes, that would probably be better in practice.  But I think this algorithm is so much cooler!  :-)
Neal Young
CC BY-SA 4.0
2012-11-03T02:59:54.793Z
2018-07-23T19:46:21.443Z
2018-07-23T19:46:21.443Z
Neal Young
<p>Is there a well-known randomized algorithm for the <a href="http://en.wikipedia.org/wiki/Set_cover_problem" rel="noreferrer">set cover problem</a> in the literature - such that it has an approximation ratio of $O(\log n)$ or $f$ - where $f$ is the max frequency of an element. please don't mention the randomized rounding method with LP (or any other method depending on LP) ? </p>

CC BY-SA 3.0
2012-11-02T03:18:22.163Z
You could run the multiplicative weight update method, but why ?
Suresh Venkat
CC BY-SA 3.0
2012-11-02T08:33:16.860Z
There is a simple and well known approximation algorithm for set cover and you can find it in first chapter of [Vazirani's](http://books.google.de/books/about/Approximation_Algorithms.html?id=EILqAmzKgYIC&redir_esc=y) book.
Saeed
CC BY-SA 3.0
2012-11-02T14:46:57.633Z
@SureshVenkat: i dont see many algorithm for the problem (other than greedy and ILP) - so I was wondering.
AJed
CC BY-SA 3.0
2012-11-02T15:28:13.507Z
@AJed This is because in the worst-case model which is generally used in TCS, the greedy algorithm is already best possible (by a celebrated result of Feige).
Yuval Filmus
CC BY-SA 3.0
2012-11-02T17:47:53.813Z
Yes, there are randomized O(log n)-approximation algorithms for set cover other than randomized rounding.  For example, to find a set cover of size K (assuming there exists one of size, say, K/(2 log n), one can start with K tokens distributed arbitrarily on the sets, then repeat the following step some T times: choose a token at random, and move it from its current set to a set S maximizing the sum of the weights of the elements in S, where the weight of an element is some function of the following: the current time step t and the current distribution of tokens on sets containing the element.
Neal Young
CC BY-SA 3.0
2012-11-02T20:45:33.977Z
@NealYoung can you please direct  me to a reference please ? [or at least give me more details on what you mean by "current distribution of tokens" ?]
AJed
CC BY-SA 3.0
2012-11-03T02:49:25.250Z
@AJed I notice you added the qualifier "well-known" to the kind of algorithm you are looking for.  This one isn't.  Anyhow the analysis is at http://greedyalgs.info/blog/grasp-set-cover/ . Algorithm is in the answer below.  (Wouldn't format well in a comment, so I had to put it in the answer field.)
Neal Young
<ds.algorithms><randomized-algorithms><set-cover>
Is there a randomized algorithm for set-cover?
AJed
# Is there a randomized algorithm for set-cover?

(Asked by: username_0 on 2012-11-02)

Is there a well-known randomized algorithm for the [set cover problem](http://en.wikipedia.org/wiki/Set_cover_problem) in the literature - such that it has an approximation ratio of $O(\log n)$ or $f$ - where $f$ is the max frequency of an element. please don't mention the randomized rounding method with LP (or any other method depending on LP) ?

**Tags:** ds.algorithms, randomized-algorithms, set-cover

> **Comments:**
> **username_1**: You could run the multiplicative weight update method, but why ?  
> **username_2**: There is a simple and well known approximation algorithm for set cover and you can find it in first chapter of [Vazirani's](http://books.google.de/books/about/Approximation_Algorithms.html?id=EILqAmzKgYIC&redir_esc=y) book.  
> **username_0**: @SureshVenkat: i dont see many algorithm for the problem (other than greedy and ILP) - so I was wondering.  
> **username_3**: @username_0 This is because in the worst-case model which is generally used in TCS, the greedy algorithm is already best possible (by a celebrated result of Feige).  
> **username_4**: Yes, there are randomized O(log n)-approximation algorithms for set cover other than randomized rounding.  For example, to find a set cover of size K (assuming there exists one of size, say, K/(2 log n), one can start with K tokens distributed arbitrarily on the sets, then repeat the following step some T times: choose a token at random, and move it from its current set to a set S maximizing the sum of the weights of the elements in S, where the weight of an element is some function of the following: the current time step t and the current distribution of tokens on sets containing the element.  
> **username_0**: @NealYoung can you please direct  me to a reference please ? [or at least give me more details on what you mean by "current distribution of tokens" ?]  
> **username_4**: @username_0 I notice you added the qualifier "well-known" to the kind of algorithm you are looking for.  This one isn't.  Anyhow the analysis is at http://greedyalgs.info/blog/grasp-set-cover/ . Algorithm is in the answer below.  (Wouldn't format well in a comment, so I had to put it in the answer field.)  

---

## 1 answers

### Answer by username_4 on 2012-11-03. Score: 9

Here's one randomized $O(\log n)$-approximation algorithm (not well known I'm afraid), for unit-cost set cover.

**input**: collection of sets over $n$ elements, upper bound $U$ on opt

**output**: w/probability $\ge 1/2$, a set cover of size $O(U \ln n)$.

1. Let $K=\lceil \ln(2n)U/0.99\rceil$. Let $T=\ln(100)$.
2. Create $K$ tokens, each with an associated unit-rate Poisson process.
3. As time $t$ increases continuously from $0$ to $T$, do the following:
   When a Poisson process fires at time $t$,
   remove its token from its current set (if any),
   then place it on a set $s$ chosen to maximize
   $$
   \sum\_{e\in s}
   \Big(
   \frac{1-1/U}{1/f(t) - 1/U}
   \Big)^{C^{(t)}\_e},
   $$
   where $C^{(t)}\_e$ denotes the number of tokens (other than the firing token)
   currently covering element $e$, and $f(t) \doteq 1-\exp(-(T-t))$.
4. Return the sets that have tokens on them.

When a token fires, it moves
to a set whose elements have largest total ``weight''.
Initially, when $t\approx 0$, the weight of element $e$
is about $.99^{C\_e} \approx 1$,
so the algorithm essentially moves tokens onto the largest sets.
When $t\approx T-\ln 2$, the weight of an element $e$ is about $.5^{C\_e}$.
Thus, each token on a set covering $e$ cuts $e$'s weight by a factor of $1/2$.
Finally, when $t\approx T-\epsilon$, an element $e$ has weight about
$\epsilon^{C\_e}$, so only uncovered (or minimally covered) elements contribute significant weight.

If $U$ is unknown,
then binary search can be used
to find the smallest integer $U$
between $1$ and $n$
for which the algorithm works.

Here is the approximation guarantee:

**Theorem.**
*If there exists a fractional set cover of size $U$,
then, with probability at least 1/2, the algorithm returns
a set cover of size at most $\lceil \ln(2n)U/0.99\rceil$.*

For the derivation and proof see <https://algnotes.info/on/obliv/greedy/set-cover-grasp/>.

### One more

Oh, and there is a well-known randomized *parallel* algorithm for set cover, namely [Primal-dual RNC approximation algorithms for set cover and covering integer programs](http://www.dcg.ethz.ch/lectures/ws0405/seminar/papers/primal_dual.pdf) by Rajagopalan and Vazirani.

> **Comments:**
> **username_1**: This looks like a reinterpretation of the multiplicative weight update method. Is it ?  
> **username_4**: No, but the underlying techniques can be used to derive both algorithms.  See [http://greedyalgs.info/blog/grasp-set-cover](http://greedyalgs.info/blog/grasp-set-cover) for the derivation (and poke around further for how the same ideas give multiplicative weights update algorithms).  
> **username_5**: Since solving the LP  approximately via multiplicative weight updates is essentially the same time as the above algorithm, I wonder if it wouldn't be better to solve the LP first and then do randomized rounding. This way, one also gets a lower bound on the optimum value and which can be used to judge the quality of the approximate solution.  
> **username_4**: Yes, that would probably be better in practice.  But I think this algorithm is so much cooler!  :-)  

---

