# Does $NP$-hardness of $c$-approximation (for some $c>1$) imply $APX$-hardness?

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!

## 1 Answer

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

• @cs_student_273 - you are welcome. – R B Dec 15 '14 at 11:04