Approximation of Set Cover I wonder why do we say $\log n$ is the best possible approximation factor for Set Cover Algorithm? We already know there exists a 2-approximation algorithm for vertex cover, which is obviously better than $\log n$. So we can use Vertex Cover algorithm to solve Set Cover problem and get a better approximation ratio. Can anyone explain this to me?
Thanks in advance
Dinur and Steurer [1] showed that assuming $P \neq NP$, there is no polynomial time algorithm which approximates set cover by a $(1-\epsilon)\ln(n)$ factor, for any constant $\epsilon &gt; 0$.
[1] https://arxiv.org/pdf/1305.1979.pdf