3
$\begingroup$

Theorem: Unless $NP \subset DTIME (n^{O(\log \log n)})$, there is no $(1-o(1))\ln n$-approximation for set cover problem.

I am a bit confused by this theorem. As we know, greedy algorithm is $(\ln n+1)$-approximation, does this mean greedy algorithm is almost the best algorithm for set cover problem?

In the wiki set cover problem, there is a very bad example about the greedy algorithm, so I think a $\ln n$-approximation is meaningless. Does the theorem above say that it is impossible to design a constant approximation algorithm?

$\endgroup$

2 Answers 2

3
$\begingroup$

The result you quote, due to Feige, has actually recently been improved by Dinur and Steurer (based on earlier work of Moshkovitz), who showed that unless $P = NP$, there is no polynomial time $(1 - o(1))\ln n$-approximation algorithm for set cover.

This result states that if all you care about is the worst case approximation ratio, then you cannot substantially improve on the trivial greedy algorithm. (There are also other algorithms achieving the same $\ln n$ bound.) In particular, no polynomial time algorithm gives a constant factor approximation for set cover on all instances.

$\endgroup$
2
$\begingroup$

Paper of P.Slavik "A Tight Analysis of the Greedy Algorithm for Set Cover" claims tight $\log m - \log\log m +\Theta(1)$ approximation factor of greedy algorithm whereas Dinur lower bound is $(1-\alpha)\log m$ for any $\alpha>0.$ So there is some (negligible) gap between the factor and the lower bound though.

$\endgroup$

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.