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.