# 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?

• How do you use the vertex cover algorithm to solve set cover? An instance of vertex cover is an instance of set cover (edges are item, vertices represent sets) but the converse is not necessarily true. (Think, e.g., of an item that belongs to 3 sets). Jan 7, 2021 at 20:44
• Thank you @Steven for your explanation. I appreciate your help Feb 2, 2021 at 6:54

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 > 0$$.
Clarification: When we say $$\ln n$$ is the best possible approximation for the set cover problem, we mean it for a general instance of the set cover. That is, there are set cover instances in which an element of the universal set could belong to more than two sets (possibly $$\Omega(n)$$ also) and for such instances, we can not achieve better than $$c \cdot \ln n$$ approximation, assuming P≠NP for any constant $$c<1$$. Therefore, this lower bound does not hold for the instances when an element belongs to just 2 sets (a.k.a. vertex cover instances). You can check this in the research paper of Dinur and Steurer, as suggested by user3209423940248.
Answer to your question: Currently, we do not know any polynomial time reduction from the set-cover instances to the vertex-cover instances. And, if you happen to find such a reduction which could give you better than $$c \cdot \ln n$$ approximation (for some constant $$c<1$$) for the set-cover problem, then you have solved the P-NP problem and you will get famous.
• Note that there is always a polytime reduction between any two NP-complete problems. However, currently, we do not know a reduction from Set Cover to Vertex Cover that could give better than $\ln n$ approximation for set cover. Jan 31, 2021 at 18:45