2
$\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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.