3
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ Sounds like the multiplicative weights update method: 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 sarielhp.org/book. $\endgroup$ – Sasho Nikolov May 3 '17 at 2:40
  • 1
    $\begingroup$ 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$ $\endgroup$ – Neal Young May 6 '17 at 1:26

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.