[Solved]: Is greedy algorithm the best algorithm for set cover problem?

Problem Detail: 

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?

Asked By : Wieshawn

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/49777

3.2K people like this

 Download Related Notes/Documents