Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
Assume that for a given minimization problem with only integer solutions, it is $NP$-hard to decide if the optimal solution is 5 or 6. I.e., a polynomial-time algorithm with an approximation ratio better than 6/5 would imply $P=NP$.
1) Does this imply that the problem is $APX$-hard as well?
2) Is there a common way of stating this inapproximability fact, besides stating that "it is $NP$-hard to approximate with an approximation ratio strictly better than 6/5"?
Thank you!
The answer for (1) is "unlikely".
It is simple to show (reduce from $Partition$) there exists no $\alpha$-approximation for Bin Packing, for any $\alpha<\frac{3}{2}$, unless $P=NP$.
That said, Crescenzi et al. have shown that unless the polynomial hierarchy collapses, Bin Packing is not APX-Hard.
As for (2), perhaps you could phrase it as "Does not admit $PTAS$ unless $P=NP$".
