3
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ Where did you see claim 2? $\endgroup$
    – Austin Buchanan
    Commented Apr 28, 2014 at 21:11
  • $\begingroup$ 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... $\endgroup$
    – a. robinson
    Commented Apr 28, 2014 at 21:17

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
0

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.