<p>Call a set <em>cheap</em> if it has cost at most <span class="math-container">$\beta/n$</span>.</p>

<p>Let <span class="math-container">$S_0$</span> 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 <em>only</em> add cheap sets whose elements are not all covered by previously added cheap sets -- this ensures that the size of <span class="math-container">$S_0$</span> is at most <span class="math-container">$n$</span>.  So, the total cost of sets in <span class="math-container">$S_0$</span> is at most <span class="math-container">$n\beta/n = \beta$</span>, and these sets cover every element that is in any cheap set.</p>

<p>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 <span class="math-container">$S_0$</span>, up front, because these sets cost at most <span class="math-container">$\beta$</span>, 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 <span class="math-container">$O(\log n)$</span> times the original optimal, the total cost (after adding in the cheap sets in <span class="math-container">$S_0$</span>) will still be <span class="math-container">$O(\log n)$</span> times the original optimal.  </p>

<p>In more detail: after committing to using the cheap sets in <span class="math-container">$S_0$</span>, the remaining problem is to compute some collection <span class="math-container">$S'$</span> of sets that covers the remaining elements --- those that aren't in any cheap set.  And <span class="math-container">$S'$</span> should have cost <span class="math-container">$O(\log n)\cdot IP^*$</span>.</p>

<p>This is the problem that the paper then shows how to solve.  To complete the details, suppose that we have some such set <span class="math-container">$S'$</span>.  Obtain the complete solution by taking <span class="math-container">$S = S_0\cup S'$</span>.  </p>

<p>This <span class="math-container">$S$</span> then covers all the elements in <span class="math-container">$U$</span> (as <span class="math-container">$S_0$</span> covers the elements that are in any cheap set, while <span class="math-container">$S'$</span> covers the rest), and the cost of <span class="math-container">$S$</span> (the  cost of <span class="math-container">$S_0$</span> plus the cost of <span class="math-container">$S'$</span>) is at most <span class="math-container">$\beta + O(\log n)\cdot IP^* = O(\log n)\cdot IP^*$</span>.  So <span class="math-container">$S$</span> is an <span class="math-container">$O(\log n)$</span>-approximate solution to the original problem.</p>

<hr>

<p>A slightly subtle point is that, to compute <span class="math-container">$S'$</span>, it is enough to compute take <span class="math-container">$S'$</span> to be any <span class="math-container">$O(\log n)$</span>-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.</p>

CC BY-SA 4.0
2018-09-25T16:05:32.247Z
2018-10-26T01:39:40.790Z
2018-10-26T01:39:40.790Z
Neal Young
<p>I was reading the paper titled "<a href="https://www.cc.gatech.edu/~mihail/D.read2010/Rajagopalan_Vazirani.pdf" rel="nofollow noreferrer">Primal-dual RNC approximation algorithms..</a>" 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 <span class="math-container">$n$</span> elements(<span class="math-container">$U$</span>) and <span class="math-container">$m$</span> sets(<span class="math-container">$S$</span>). Each set has a positive weight. Let <span class="math-container">$E_v$</span> holds the sets in which the element <span class="math-container">$v$</span> is present. Let <span class="math-container">$\beta =$</span>max<span class="math-container">$_{v \in U}$</span> min<span class="math-container">$_{s \in E_v}$</span> weight(s). Let also <span class="math-container">$IP^*$</span> is the weight of an optimal set cover. It is easy to see, <span class="math-container">$IP^*\geq \beta$</span>. 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 <span class="math-container">$\leq \beta/n$</span>. Since there are <span class="math-container">$n$</span> elements the additional cost is at most <span class="math-container">$\beta$</span>. Then they claim that, "<strong>Since <span class="math-container">$\beta$</span> is a lower bound on <span class="math-container">$IP^*$</span>, this cost is subsumed in the approximation. "</strong> And this is the statement I did not understand. </p>

CC BY-SA 4.0
2019-04-08T20:51:19.853Z
Cross-posted here: https://cs.stackexchange.com/questions/97703/about-a-pre-processing-step-for-primal-dual-weighted-set-cover-problem?rq=1
Neal Young
CC BY-SA 4.0
2019-04-24T22:01:13.120Z
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.
Chandra Chekuri
<approximation-algorithms><set-cover>
About a pre-processing step for primal–dual weighted set cover problem
user2104150
# About a pre-processing step for primal–dual weighted set cover problem

(Asked by: username_0 on 2018-09-23)

I was reading the paper titled "[Primal-dual RNC approximation algorithms..](https://www.cc.gatech.edu/~mihail/D.read2010/Rajagopalan_Vazirani.pdf)" 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.

**Tags:** approximation-algorithms, set-cover
> **Comments:**
> **username_1**: Cross-posted here: https://cs.stackexchange.com/questions/97703/about-a-pre-processing-step-for-primal-dual-weighted-set-cover-problem?rq=1  
> **username_2**: 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.  

---

## 1 answers

### Answer by username_1 on 2018-09-25. Score: 0 | Accepted 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.


---

