# Clarification on the inapproximability of set cover

I'm trying to understand the inapproximability of the minimum set cover problem.

The wikipedia page states that it is hard to approximate within a factor of $(1-o(1))\ln n$ and that $n$ refers to the size of the ground set. It references the work of Dinur and Steurer (2013) who state that, for every $\varepsilon>0$, it is NP-hard to approximate min set cover within a factor of $(1-\varepsilon)\ln n$ where $n$ refers to the size of the instance. It seems they don't define what they mean by "size of the instance," but I take that to mean an encoding of the instance (which takes more space than just the size of the ground set).

Would I be correct in saying that set cover is hard to approximate within a factor of $(1-\varepsilon)\ln N$, where $N$ is the size of the ground set plus the sizes of all the subsets? Or, if $N$ is the size of the ground set plus the number of subsets?

• The Dinur & Steurer paper provides a citation into the literature for an earlier $(1-o(1)) \ln n$ result: on p.4 they mention an earlier result of Feige. So, you might find it helpful to read Feige's paper to see if it answers your question. – D.W. Jul 21 '16 at 19:05
• @D.W. Feige is indeed clearer. He says that $s$ (the number of subsets) is less than $n$ (the number of points to cover) in his reductions. Still not sure what Dinur and Steurer meant though – Austin Buchanan Jul 21 '16 at 19:20

The hardness proof appears in an earlier paper of Moshkovitz, The Projection Games Conjecture and The NP-Hardness of ln n-Approximating Set-Cover; Dinur and Steurer proved a version of the Projection Games Conjecture, thus completing the NP-hardness proof. Moshkovitz clearly states that $n$ is the size of the universe, and she also assumes that the number of sets is polynomial in $n$.
Feige had proved earlier that if you can approximate set cover better than $\ln n$ then $\mathsf{NP}\subseteq \mathsf{DTIME}(N^{\log\log N})$. He improved on earlier result of Lund and Yannakakis which showed a hardness of $0.72\ln n$ under the same assumption.
The threshold $\ln n$ (where $n$ is the size of the universe) is important since it is achieved by the greedy algorithm. The analysis of the greedy algorithm shows that after $OPT \cdot t$ steps (where $OPT$ is the size of an optimal solution), we have covered a $1-e^{-t}$ fraction of the universe. When $e^{-t} < 1/n$, we have covered the entire universe (since we cover more than $n-1$ elements). Hence after at most $t = OPT \cdot \ln n$ steps, the greedy algorithm manages to cover the entire universe. This is where the dependence on the size of the universe comes from.
• So we cannot claim (under current knowledge) that it is NP-hard to get a $(1-\varepsilon)\ln n$ approximation when $s \le n$? – Austin Buchanan Jul 21 '16 at 22:04
• I corrected the phrasing in my comment. To be clear: per Feige's notation, $s$ is the number of subsets – Austin Buchanan Jul 21 '16 at 22:08