Is there a randomized algorithm for set-cover?

Question

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) ?

Answer 1

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.