# Is there a randomized algorithm for set-cover?

Is there a well-known randomized algorithm for the 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) ?

• You could run the multiplicative weight update method, but why ? – Suresh Venkat Nov 2 '12 at 3:18
• There is a simple and well known approximation algorithm for set cover and you can find it in first chapter of Vazirani's book. – Saeed Nov 2 '12 at 8:33
• @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 Nov 2 '12 at 15:28
• 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 Nov 2 '12 at 17:47
• @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 Nov 2 '12 at 20:45

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 by Rajagopalan and Vazirani.

• This looks like a reinterpretation of the multiplicative weight update method. Is it ? – Suresh Venkat Nov 6 '12 at 16:48
• No, but the underlying techniques can be used to derive both algorithms. See 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 Dec 8 '12 at 3:12
• 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 Jul 12 '17 at 1:23