Problem with understanding the lower bound of OPT in Greedy Set Cover approximation algorithm From what I know of analyzing and designing approximation algorithms, we need to find a lower bound on the optimum (in the case of minimization). For example if our solution is greedy ($SOL_G$) and if we find a lower bound $L_B$ on $OPT$ then $$L_B \leq OPT$$

and if we correctly analyze the following $$SOL_G \leq f . L_B$$ Then we can conclude that $$SOL_G \leq f. OPT$$ where $f$ is the approximation factor of our greedy solution.

Vijay Vazirani in his book approximation algorithm on page 16 proposed the Greedy Set cover and his analysis of the lower bound on the optimum (Lemma 2.3). I have problem with understanding this Lemma: 

From his convention at the beginning of the book, $OPT$ stands for the optimum solution of the problem instance (not the optimum that is obtained by the approximation algorithm).

At the beginning of the Lemma he says 


  In any iteration, the leftover sets of the optimal solution can cover the remaining elements at a cost of at most OPT 


It is clear because $\sum_{e \in U} price(e) = OPT$. (The price assignment is based on the selection of the sets)

In the next sentence he says


  Therefore, among these
  sets, there must be one having cost-effectiveness of at most $OPT/|\bar{C}|$ where $\bar{C} = U - C$


and $C$ is the current list of selected sets.

I can't understand, why is it true? $OPT$ is the optimum of problem instance not the algorithm. Because in the algorithm the price of each set is distributed among its elements, it seems he uses this fact but $OPT$ is not about the algorithm! it is the optimum of problem instance

Thanks.
Let's assume for simplicity that $C = \emptyset$; I'll let you work out the general case. Note that there are at most $|U|$ sets in OPT. Let $OPT = \{O_1,\ldots,O_m\}$, where $m \leq |U|$. We have
$$
\sum_{i=1}^m \frac{c(O_i)}{|O_i|} \frac{|O_i \setminus (O_1 \cup \cdots \cup O_{i-1})|}{|U|} \leq \sum_{i=1}^m \frac{c(O_i)}{|O_i|} \frac{|O_i|}{|U|} = \frac{OPT}{|U|}.
$$
On the left-hand side we have a weighted average of the quantities $c(O_i)/|O_i|$, so one of them must be at most $OPT/|U|$. The greedy algorithm selects a set $S$ with $c(S)/|S|$ minimal, so in particular
$$
\frac{c(S)}{|S|} \leq \min\left(\frac{c(O_1)}{|O_1|},\ldots,\frac{c(O_m)}{|O_m|}\right) \leq \frac{OPT}{|U|}.
$$