2
$\begingroup$

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

$\endgroup$
2
  • 4
    $\begingroup$ 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). $\endgroup$
    – Steven
    Jan 7, 2021 at 20:44
  • $\begingroup$ Thank you @Steven for your explanation. I appreciate your help $\endgroup$
    – Mark97
    Feb 2, 2021 at 6:54

2 Answers 2

3
$\begingroup$

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

[1] https://arxiv.org/pdf/1305.1979.pdf

$\endgroup$
1
  • $\begingroup$ Yes, that I understood. I just wanted to know if it's possible to reduce the problem to vertex cover and run the approximation algorithm of vertex cover in it to get a better bound. But thanks for your answer $\endgroup$
    – Mark97
    Jan 11, 2021 at 17:06
3
$\begingroup$

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.

However, assuming P≠NP, such a reduction is not possible.

$\endgroup$
2
  • $\begingroup$ Thank you dear for such a nice clarification $\endgroup$
    – Mark97
    Jan 8, 2021 at 20:06
  • $\begingroup$ 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. $\endgroup$ Jan 31, 2021 at 18:45

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.