3
$\begingroup$

Just a question for personal comprehension. Consider the following statement:

It is NP-hard to approximate Set-Cover within a $(1 - \epsilon) \log n$ factor for any $0 < \epsilon < 1$.

Now, NP-hardness refers to decision problems.So what is NP-Hard exactly here ?

My guess is that the statement is equivalent to saying that the following problem is NP-hard (but I really ain't sure):

Given a set cover instance $S$ and an integer $k$ with the guarantee that either $S$ admits a cover of size at most $k$, or $S$ has a cover of size at least $k \cdot (1 - \epsilon) \log n$, decide if $S$ has a cover of size at most $k$.

Note that I took set cover as an example, but my question is on problems that are said 'hard to approximate' in general.

$\endgroup$
2
$\begingroup$

Your guess is correct. The formal statement corresponding to the informal one goes like this:

For every $\epsilon > 0$ and every language $L$ in NP there exists a polytime reduction $f$ mapping instances of $L$ to instances of set cover $(F,m)$ (where $F$ is a set system and $m$ is the target number of sets) such that:

  • If $x \in L$ then $f(x)$ has a cover with $m$ sets, and

  • If $x \notin L$ then every cover of $f(x)$ requires at least $(1-\epsilon)\ln n \cdot m$ sets, where $n$ is the size of the universe.

For this more accurate version, see Claim 4.2 in Dana Moshkovitz, The projection games conjecture and the NP-hardness of $\ln n$-approximating set cover.

A statement claiming that a certain approximation problem is NP-hard to approximate better than some factor should always be interpreted in this way.

$\endgroup$
  • $\begingroup$ Thank you for your answer. So I guess I could have the same formulation for, say, CLIQUE - i.e. there is an $f$ mapping $x \in L$ to a graph with clique number $\geq m$, and $x \notin L$ to a graph with clique number $\leq 1/(n^{1-\epsilon}) m$. Does that sound right ? $\endgroup$ – Manuel Lafond Dec 2 '15 at 15:44
  • $\begingroup$ Yes, this sounds right. You can always look at the paper if you want to be sure. $\endgroup$ – Yuval Filmus Dec 2 '15 at 17:10
3
$\begingroup$

Most likely what is meant is the following statement:

If $P \ne NP$, then there is no polynomial-time approximation algorithm for Set-Cover that achieves a $(1-\epsilon) \log n$ approximation factor.

Or, equivalently: the existence of a polynomial-time approximation algorithm for Set-Cover that achieves a $(1-\epsilon) \log n$ approximation factor implies that $P=NP$.


Your proposed formulation at the end of your question might look tempting, but if you want to understand how to formalize the claim, I probably wouldn't suggest formalizing it that way -- that formulation introduces unfamiliar technical issues of its own. The problem you listed is a promise problem (it's not a decision problem). Promise problems are weird and some of your intuition that you've built up won't work quite right for promise problems. Promise problems are weird and counter-intuitive; if you want to build your intuition, often it's best to simply avoid them, rather than try to absorb the messy details involved in formalizing them.

$\endgroup$
  • $\begingroup$ +1 Thank you for your answer. I accepted Yuval's answer since it corresponds a bit more to what I was looking for - but still thanks. If you have any comments on his answer they're welcome. $\endgroup$ – Manuel Lafond Dec 2 '15 at 15:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.