5
$\begingroup$

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

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

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.

$\endgroup$
  • $\begingroup$ This looks like a reinterpretation of the multiplicative weight update method. Is it ? $\endgroup$ – Suresh Venkat Nov 6 '12 at 16:48
  • $\begingroup$ 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). $\endgroup$ – Neal Young Dec 8 '12 at 3:12
  • 1
    $\begingroup$ 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. $\endgroup$ – Chandra Chekuri Jul 12 '17 at 1:23

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.