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?


1 Answer 1


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$.

  • 2
    $\begingroup$ Alternatively, Slavik is interested in the worst possible approximation ratio, as a function of $m$. $\endgroup$ Commented Jul 16, 2022 at 20:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.