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.
-
$\begingroup$ Cross-posted here: cs.stackexchange.com/questions/97703/… $\endgroup$– Neal YoungApr 8, 2019 at 20:51
-
$\begingroup$ By now more general methods are known to get O(log n) approximation for Set Cover. One can solve the LP relaxation in parallel (see Neal Young's papers) and then rounding is pretty simple. $\endgroup$– Chandra ChekuriApr 24, 2019 at 22:01
1 Answer
Call a set cheap if it has cost at most $\beta/n$.
Let $S_0$ be the collection of sets obtained by "scanning through the sets and adding any cheap sets". This wording is not quite right. In this step one should only add cheap sets whose elements are not all covered by previously added cheap sets -- this ensures that the size of $S_0$ is at most $n$. So, the total cost of sets in $S_0$ is at most $n\beta/n = \beta$, and these sets cover every element that is in any cheap set.
The intuition is that, if we're willing to give up a factor of two in the performance guarantee, we can go ahead and add the cheap sets, in $S_0$, up front, because these sets cost at most $\beta$, which is a lower bound on the optimal cost. Once we've done this, all that remains is to cover the elements that are not covered by any cheap set. If we can do this using sets that have cost $O(\log n)$ times the original optimal, the total cost (after adding in the cheap sets in $S_0$) will still be $O(\log n)$ times the original optimal.
In more detail: after committing to using the cheap sets in $S_0$, the remaining problem is to compute some collection $S'$ of sets that covers the remaining elements --- those that aren't in any cheap set. And $S'$ should have cost $O(\log n)\cdot IP^*$.
This is the problem that the paper then shows how to solve. To complete the details, suppose that we have some such set $S'$. Obtain the complete solution by taking $S = S_0\cup S'$.
This $S$ then covers all the elements in $U$ (as $S_0$ covers the elements that are in any cheap set, while $S'$ covers the rest), and the cost of $S$ (the cost of $S_0$ plus the cost of $S'$) is at most $\beta + O(\log n)\cdot IP^* = O(\log n)\cdot IP^*$. So $S$ is an $O(\log n)$-approximate solution to the original problem.
A slightly subtle point is that, to compute $S'$, it is enough to compute take $S'$ to be any $O(\log n)$-approximate solution to the problem with universe restricted to the elements not covered by any cheap set. This is because the optimal cost for the restricted problem is at most the optimal cost for the original problem.
