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!
Does $NP$-hardness of $c$-approximation (for some $c>1$) imply $APX$-hardness?
cc.complexity theory;np hardness;approximation hardness;apx
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$.