Theorem 2.3 — the unweighted algorithm covers $X'$ with $|\mathcal C|\le\lceil 4\ln n\rceil\,|\mathcal C_{OPT}|(\log_2 m+2)$

Let a set-cover instance have a ground set of $n\ge2$ elements and $m$ sets, all of unit cost. Let $\sigma$ be any sequence of elements given by the adversary (the set $X'$ of given elements), and let $\mathcal C_{OPT}$ be any family of sets covering every element of $\sigma$. Then:

1. the unweighted online algorithm of Section 2 has a run on $\sigma$ (at every arrival an admissible choice exists), and
2. every run of the algorithm on $\sigma$ ends with a cover $\mathcal C$ that is a feasible cover of $X'$ (every element of $\sigma$ lies in some member of $\mathcal C$) and satisfies

In particular the algorithm is $O(\log m\log n)$-competitive for unweighted online set cover: the paper writes $|\mathcal C|=O(|\mathcal C_{OPT}|\log m\log n)$, and its proof yields the explicit bound above (Lemma 2.1 times Lemma 2.2).

Formalization Note The paper writes $O(\cdot)$; the proof yields the constant $\lceil 4\ln n\rceil\cdot(\log_2 m+2)$, where $\lceil 4\ln n\rceil$ is the paper's "$4\log n$" sets per augmentation (natural logarithm, rounded up) and $\log_2 m+2=\log_2(4m)$. The hypothesis $n\ge2$ is the paper's tacit assumption behind $\log n$: for $n=1$ no set may be added and the arriving element stays uncovered. Since the algorithm's choice in step 2(c) is not determined, it is a relation, and part 1 (existence of a run) is part of the statement. Arrival lists may repeat elements.