If you want to make money online : Register now

[Solved]: Hardness of approximating hitting set

, , No Comments
Problem Detail: 

Consider the hitting set problem with $n$ elements and $m$ sets. I gather from the linked page as well as this that

1) it is NP-hard to approximate the cost of the optimal solution to a multiplicative factor of $c \log n$ for some $c>0$.

2) it is NP-hard to approximate the cost of the optimal solution to a multiplicative factor of $c \log m$ for some $c>0$.

3) it is NP-hard to approximate the cost of the optimal solution to a multiplicative factor of $c \log \max(n,m)$ for some $c>0$.

Is my understanding correct? This seems to be a straightforward consequence of what is on the internet, but some of the notation in these sources is mysterious to me and I want to make sure I'm not misunderstanding.

Asked By : a. robinson

Answered By : Yuval Filmus

For every choice of $\alpha > 0$, Moshkovitz shows that approximating set cover on instances with $n^{C_\alpha}$, where $C_\alpha$ is some constant depending only on $\alpha$, better than $(1-\alpha) \log n$ is NP-hard. Since $\log m \leq C_\alpha \log n$, it is NP-hard to approximate set cover better than $\frac{1-\alpha}{C_\alpha} \log m$. I'm not sure what is $\sup_{\alpha\to 1} \frac{1-\alpha}{C_\alpha}$, but it can probably be gleaned from the paper. At any rate, all three results you mention are correct, and the first can be strengthened by replacing $c$ with $1-\alpha$ for any $\alpha > 0$.

Best Answer from StackOverflow

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

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback