# Hardness of approximating hitting set

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.

• Where did you see claim 2? Apr 28 '14 at 21:11
• The Moshkovitz paper takes $m={\rm poly}(n)$. If this means something like $m=n^3$, then $\log m$ and $\log n$ are within a multiplicative constant factor, and claims (1) and (2) are equivalent. In general, however, I"m a little confused about what $m={\rm poly}(n)$ means. Does this means $m$ is a polynomial in $n$ of some fixed degree independently of problem parameters, like, e.g., $3$? Is this degree just some constant that is not computed, or can it be arbitrary? Not being a CS person, I'm not really familiar with the conventions about what this sort of thing should mean... Apr 28 '14 at 21:17

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