# About a pre-processing step for primal-dual weighted set cover problem

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.

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.
• 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? Sep 25 '18 at 14:18
• 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. Sep 25 '18 at 15:09