The greedy charge on each newly covered element is at most OPT divided by the remaining count

Fix a step of the greedy run, let $R$ be the set of elements still uncovered just before it and $r=\mathrm{\mid }R\mathrm{\mid }\ge 1$ the remaining count; let $N\subseteq R$, $N\mathrm{\ne }\mathrm{\varnothing }$, be the set of elements newly covered by the set chosen at this step, so the chosen price per newly covered element is $c\mathrm{/}\mathrm{\mid }N\mathrm{\mid }$ for that set's cost $c$. Put $t_S=\mathrm{\mid }S\cap R\mathrm{\mid }$ for every set $S$ of the fixed minimum-cost cover $O^{\ast }$ of [F2]. Since $O^{\ast }$ covers $U$ and hence $R$, every element of $R$ lies in at least one $S\in O^{\ast }$; summing the counts $t_S$ therefore counts each element of $R$ at least once, so ${\sum }_{S\in O^{\ast }}{t}_S\ge r\ge 1$.

Let $T=\{S\in O^{\ast }:t_S>0\}$. Then $T$ is nonempty because ${\sum }_{S\in O^{\ast }}{t}_S\ge r\ge 1$, and ${\sum }_{S\in T}{t}_S={\sum }_{S\in O^{\ast }}{t}_S\ge r>0$, while ${\sum }_{S\in T}c(S)\le {\sum }_{S\in O^{\ast }}c(S)=\mathrm{O}\mathrm{P}\mathrm{T}$ because all costs are nonnegative and $T\subseteq O^{\ast }$. The $t_S$-weighted average of the ratios $c(S)\mathrm{/}{t}_S$ over $S\in T$ equals $({\sum }_{S\in T}c(S))/\left({\sum }_{S\in T}{t}_S\right)$ and is therefore at least the minimum of those ratios, so that minimum is at most $\mathrm{O}\mathrm{P}\mathrm{T}\mathrm{/}r$.

Each $S\in T$ is a listed set of the instance and has positive newly covered count $t_S>0$ at this step, so it is a candidate in the greedy choice; by [F1] the chosen set minimizes the ratio among all candidates, so the chosen price per newly covered element satisfies $c\mathrm{/}\mathrm{\mid }N\mathrm{\mid }\le {\min }_{S\in T}c(S)\mathrm{/}{t}_S\le \mathrm{O}\mathrm{P}\mathrm{T}\mathrm{/}r$. Every element newly covered at this step receives the charge $c\mathrm{/}\mathrm{\mid }N\mathrm{\mid }$, hence a charge of at most $\mathrm{O}\mathrm{P}\mathrm{T}\mathrm{/}r$.

Order the elements of $U$ by the round in which they are first covered, breaking ties within a round by the fixed order of $U$, and let $u$ be the $j$-th element of this order, covered in a round that begins with $r$ uncovered elements. Before that round exactly $n-r$ elements are already covered, all of them earlier than $u$ in the order, so $j\ge n-r+1$, that is, $r\ge n-j+1\ge 1$; since the charge of $u$ is at most $\mathrm{O}\mathrm{P}\mathrm{T}\mathrm{/}r$ by step 3.1 and $r\ge n-j+1>0$, it is at most $\mathrm{O}\mathrm{P}\mathrm{T}\mathrm{/}(n-j+1)$.

Consequently the price chosen in any greedy step with $r\ge 1$ uncovered elements is at most $\mathrm{O}\mathrm{P}\mathrm{T}\mathrm{/}r$, and the $j$-th element in first-coverage order receives charge at most $\mathrm{O}\mathrm{P}\mathrm{T}\mathrm{/}(n-j+1)$ for every $j=1,\dots ,n$; both bounds are ordinary inequalities of nonnegative rationals with positive denominators, so no division by zero occurs.