# Lower Bounding Set Cover's Approximation Ratio

I am reading Slavik's paper A Tight Analysis of Greedy Set Cover. Specifically, Slavik considers the unweighted version of set cover where the ground set is $${U = \{1,\ldots,m\}}$$ for arbitrarily large $$m$$. There is a collection of subsets $${S = \{S_1,\ldots,S_n\}}$$ that is a cover of $$U$$. The goal is to find the smallest subcover $${S^* \subset S}$$ that is a cover of $$U$$.

Let $${\textrm{Opt}:= \vert S^* \vert}$$ be the size of the optimal solution and let $$G$$ be the size of the solution found by the traditional greedy algorithm that selects the subset that covers the most remaining elements. Slavik proves a bound that (see Eqs. (1) and (2))

$$\ln m - \ln\ln m - 0.31 < \frac{G}{\textrm{Opt}} < \ln m - \ln\ln m + 0.78$$

What confuses me is how the approximation ratio can be lower bounded by a function of $$m$$. It seems to me that for arbitrary $$m$$, it would be possible for $${\frac{G}{\textrm{Opt}} = 1}$$ (e.g., let $$S_1 \in S$$ be set $${\{1,\ldots,m-1\}}$$ and let $${S_2 \in S}$$ be set $${\{m\}}$$ in which case it seems $${G = \textrm{Opt} = 2}$$).

Clearly, I am missing something fundamental. Am I misunderstanding the lower bound on the approximation ratio entirely?

Yes. You should read the lower bound as: there exists an instance with $$m$$ items such that $$\frac{G}{\text{Opt}} \ge \log m - \log \log m - 0.31$$.
• Alternatively, Slavik is interested in the worst possible approximation ratio, as a function of $m$. Jul 16, 2022 at 20:42