An instance is specified by a collection $S$ of subsets of a universe $U$ and a cost vector $c$, where $c_s\ge 0$ is the cost of set $s\in S$. A (fractional set) cover $x$ assigns a non-negative weight $x_s$ to each set $s\in S$. The size of the cover is $|x| = \sum _s x_s$. The cost of the cover is $c\cdot x = \sum _s c_s x_s$. Its coverage is $\min _{e\in U} x(e)$. Its coverage of element $e$ is $x(e) = \sum _{s\ni e} x_e$. The cover is feasible if its coverage is at least 1. The goal is to find a minimum size feasible cover.

The cover is an integer cover if each $x_s$ is an integer.

Given the state $S_t$ after $t$ samples, define $\phi _t ~ =~ \log _{1-\varepsilon } \sum _{j=1}^n \big(1-\varepsilon \big)^{\textstyle y^t(j)}.$

Note that $\phi _t$ is a lower bound on the minimum of the values at time $t$:

After the first $t$ steps, let $\omega _j$ denote the term for $j$ in the sum in $\phi _t$, so $\phi _t = \log _{1-\varepsilon } \sum _{j=1}^n \omega _j$.

Let $\delta _j = y^{t+1}(j) - y^t(j)$ denote the increase in the $j$th counter in the next step. By calculation, using that $\delta _j \in [0,1]$ and $\log _{1-\varepsilon } 1-\varepsilon z \ge (1-\varepsilon )z$,

For any $j$, the expectation of $\delta _j$ is at least $\mu$, so, by (\ref{eq:1}), the expectation of $\phi _{t+1}-\phi _t$, given $\phi _t$ is

Thus, in expectation, $\phi$ increases by at least $(1-\varepsilon )\mu$ in each iteration. By Wald’s equation,

Since $\min _j y^T(j)\ge \phi _T$, the lemma follows.

Since $C$ is an integer, and the rounding scheme stops sampling when $\tilde x$ has coverage at least $C$, the final cover $\tilde x$ inevitably has coverage exactly $C$.

By Wald’s equation, the total expected cost of all the samples is the expected number of samples, $\textrm{E}[T]$, times the expected cost per sample, which is $c\cdot x/|x|$. To finish we show that $\textrm{E}[T]$ is at most $|x|/(1-2\varepsilon )$.

For any element $e\in U$, with each sample, the probability that the sampled set contains $e$ is $\sum _{s\ni e} x_s /|x|$, which, since $x$ has coverage $C$, is at least $\mu = C/|x|$. Thus, with each sample, the expected increase in the coverage of each element is at least $\mu$. Applying the Chernoff variant to the coverages of the $n$ elements, the expectation of the coverage of any element at termination is at least $(1-\varepsilon )(\mu \textrm{E}[T] \, -\, \varepsilon ^{-1}\ln n)$. Since the coverage at termination is inevitably $C$,

Rewriting and using the assumption on $C$,

This implies $\textrm{E}[T]/|x| \le (1+\varepsilon )/(1-\varepsilon ) \lt 1/(1-2\varepsilon )$.

The algorithm will emulate the rounding scheme, but instead of choosing each set $s$ randomly, it will choose each set so as to keep the conditional expectation of the final cost below $c\cdot x/(1-2\varepsilon )$.

Recall that $T$ is the total number of samples, and, for each $t=0,\ldots ,T$, the “state” $S_t$ consists of the sequence of the first $t$ samples. To get the pessimistic estimator, we first bound the expected number of remaining samples, $\textrm{E}[T-t~ | S_t]$, given the state after $t$ samples.

Define $\mu =C/|x|$ as in the proof of the second lemma, and $\phi _t$ as in the proof of the Chernoff variant. As shown the proof of the variant, with each sample, $\phi _t$ decreases in expectation by at least $(1-\varepsilon )\mu$. But $\phi _T$ is finally at least $C$. So, by Wald’s equation, the expected number of samples remaining, $\textrm{E}[T-t~ |~ \phi _t]$, is at most $(\phi _t - C) / (1-\varepsilon )\mu$.

Given $S_t$, the expected final cost is the cost of the sets in $S_t$ plus the expected cost of the remaining sets. By Wald’s equation (since each sample costs $c\cdot x/|x|$ in expectation) the expected cost of the remaining sets is $\textrm{E}[T-t\, |\, \phi _t]$ times $c\cdot x/|x|$. Substituting in the bound on $\textrm{E}[T-t\, |\, \phi _t]$ from the previous paragraph, the expected final cost, given $S_t$, is at most

The algorithm will choose each set to keep this pessimistic estimator from increasing. Given $\psi _t$, if it chooses the next set to be $s$, using Bound (\ref{eq:1}) from the proof of the Chernoff variant, the increase $\psi _{t+1}-\psi _t$ in the pessimistic estimator is

where $\omega _e = (1-\varepsilon )^{\tilde x^t(e)}$ and $\mu =C/|x|$.

If $s$ is chosen randomly, then (since $\Pr [e\in s] \ge \mu$ for all $e$ and $\textrm{E}[c_s] = c\cdot x/|x|$) the expectation of the right-hand-side above is non-positive. Thus, some choice of set $s$ makes it non-positive. Rearranging terms to gather on the left those that depend on $s$, it is non-positive iff

Since the algorithm chooses $s$ to maximize the left-hand side above, it keeps the pessimistic estimator from increasing. Thus, the algorithm keeps the conditional expectation of the final cost below $c\cdot x/(1-\varepsilon )$. This proves the theorem.