1
$\begingroup$

I was reading the paper titled "Primal-dual RNC approximation algorithms" by Rajagopalan and Vazirani. I have a problem of understanding the Lemma 4.1.1.

They present a dual fitting based algorithm for weighted set cover. First let me set up the required concept to clarify where I am having trouble. Suppose we have $n$ elements ($U$) and $m$ sets ($S$). Each set has a positive weight. Let $E_v$ holds the sets in which the element $v$ is present. Let $\beta =$max$_{v \in U}$ min$_{s \in E_v}$ weight(s). Let also $IP^*$ is the weight of an optimal set cover. It is easy to see, $IP^*\geq \beta$.

Now assume we have an approximation algorithm for weighted set cover. What the paper is saying in the lemma is that you can do a pre-processing before starting the approximation algorithm as follows. You can scan through the sets and add any sets that have weight $\leq \beta/n$. Since there are $n$ elements the additional cost is at most $\beta$. Then they claim that

Since $\beta$ is a lower bound on $IP^*$, this cost is subsumed in the approximation. And this is the statement I did not understand.

$\endgroup$
1
$\begingroup$

The goal is to give an $O(\log n)$ approximation algorithm, starting with an algorithm that is already an $O(\log n)$ approximation algorithm, and optimizing it further. Adding the low cost elements results in an approximation ratio of $1 + O(\log n) = O(\log n)$, since the total weight of sets we add is $\beta$, which is also an upper bound on the value of the optimal solution.

$\endgroup$
  • $\begingroup$ Thank you. So what you are saying is like that, if APPROX $\leq$ (logn) OPT then it is also $\leq$ (logn+1) OPT. Since OPT > $\beta$, APPROX $\leq$ (logn) + $\beta$. Am I right? $\endgroup$ – user2104150 Sep 25 '18 at 14:18
  • $\begingroup$ What I’m saying is that adding sets of weight $\beta$ only deteriorates the approximation factor by additive 1, which makes little difference here since we’re aiming at a logarithmic approximation ratio. $\endgroup$ – Yuval Filmus Sep 25 '18 at 15:09
  • $\begingroup$ Thanks. So if we had a constant approx. ratio it would not work? $\endgroup$ – user2104150 Sep 25 '18 at 15:24
  • $\begingroup$ It would still work, but the constant would be affected. $\endgroup$ – Yuval Filmus Sep 25 '18 at 15:43

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.