<p>I remember that I saw once an alternative to the greedy set cover algorithm that works as follows:</p>

<ol>
<li>Assign weight 1 to every element in the universe. Repeat steps 2 and 3 until the universe is covered:</li>
<li>Pick a set for which the sum of weights of all the elements it contains is maximal.</li>
<li>Double the weights of all uncovered elements.</li>
</ol>

<p>I remember that it was also log(n) approximation, though I don't know how to show it. Is there some known technique for that kind of algorithms, in which appropriate global weight/cost on all the elements can give some approximation guarantees?</p>

CC BY-SA 3.0
2017-05-03T02:40:22.187Z
Sounds like the multiplicative weights update method: http://www.satyenkale.com/papers/mw-survey.pdf. This book by Sariel Har-Peled also has a chapter on this (Approximation by Reweighting), which includes a constant factor approximation for geometric set cover http://sarielhp.org/book/.
Sasho Nikolov
CC BY-SA 3.0
2017-05-06T01:26:31.497Z
Define potential $\phi_k$ to be the sum of all element weights after $k$ iterations, so $\phi_0=n$.  In any iteration, the greedy choice ensures $\phi_{k+1} \le 2(1-1/2\mbox{OPT})\phi_k$ (to prove this compare greedy to expected change for a set chosen randomly from OPT).  So inductively $$\phi_{k} \le 2^k(1-1/2\mbox{OPT})^k n < 2^k\exp(-k/2\mbox{OPT})n.$$  So after $k=2\mbox{OPT}\ln n$ rounds, the potential is less than $2^k$, so all elements are covered.  To expand on "prove this..", let $\phi_{ke}$ be the weight of $e$, then $\phi_{k+1} \le 2[\phi_k - 0.5\sum_{e\in S} \phi_{ke}]\ldots$
Neal Young
<approximation-algorithms><set-cover>
Alternative Set Cover Algorithm With Doubling
jerry
# Alternative Set Cover Algorithm With Doubling

(Asked by: username_0 on 2017-05-03)

I remember that I saw once an alternative to the greedy set cover algorithm that works as follows:

1. Assign weight 1 to every element in the universe. Repeat steps 2 and 3 until the universe is covered:
2. Pick a set for which the sum of weights of all the elements it contains is maximal.
3. Double the weights of all uncovered elements.

I remember that it was also log(n) approximation, though I don't know how to show it. Is there some known technique for that kind of algorithms, in which appropriate global weight/cost on all the elements can give some approximation guarantees?

**Tags:** approximation-algorithms, set-cover
> **Comments:**
> **username_1**: Sounds like the multiplicative weights update method: http://www.satyenkale.com/papers/mw-survey.pdf. This book by Sariel Har-Peled also has a chapter on this (Approximation by Reweighting), which includes a constant factor approximation for geometric set cover http://sarielhp.org/book/.  
> **username_2**: Define potential $\phi_k$ to be the sum of all element weights after $k$ iterations, so $\phi_0=n$.  In any iteration, the greedy choice ensures $\phi_{k+1} \le 2(1-1/2\mbox{OPT})\phi_k$ (to prove this compare greedy to expected change for a set chosen randomly from OPT).  So inductively $$\phi_{k} \le 2^k(1-1/2\mbox{OPT})^k n < 2^k\exp(-k/2\mbox{OPT})n.$$  So after $k=2\mbox{OPT}\ln n$ rounds, the potential is less than $2^k$, so all elements are covered.  To expand on "prove this..", let $\phi_{ke}$ be the weight of $e$, then $\phi_{k+1} \le 2[\phi_k - 0.5\sum_{e\in S} \phi_{ke}]\ldots$  

---

## 0 answers

