Lemma 3.3 — an augmentation step never increases the potential, so the algorithm never fails

Let $\alpha > 0$ and consider the potential

of the weighted online set-cover algorithm (Section 3), where $n = |X|$, $w_j = \sum_{S \ni j} w_S$, and $C$ is the set of elements covered by $\mathcal C$.

1. For any weights $w$, any cover $\mathcal C$ and any set $S$ with $w_S \ge 0$ and $c_S \le \alpha$, the per-set substep of a weight augmentation for $S$ (multiply $w_S$ by $1 + \frac{1}{n c_S}$; if $S \notin \mathcal C$, add $S$ when this does not increase $\Phi$; FAIL if $\Phi$ has increased) does not fail, and the resulting weights $w'$ and cover $\mathcal C'$ satisfy

2. In particular, if every set costs at most $\alpha$, then on every arrival sequence the algorithm never reaches FAIL.

The hypothesis $c_S \le \alpha$ is the paper's footnote 1 (p. 367): the algorithm has discarded every set costing more than $\alpha \ge c(\mathcal C_{OPT})$. The proof needs it in step (5): the inequality $e^y - 1 \le 3y/2$ holds only for $0 \le y \le 1/2$, with $y = c_S/(2\alpha)$.

This lemma is what keeps $\Phi$ below $n^2$ for the whole run, the invariant behind both parts of Theorem 3.4.

Formalization Note Part 1 is stated for arbitrary weights with $w_S \ge 0$ rather than only for weights the algorithm reaches; the algorithm's weights are always positive. Part 2 assumes only $c_S \le \alpha$ for every set, which is how the proof uses $\alpha \ge c(\mathcal C_{OPT})$.