<p>The answer for (1) is "unlikely".</p>

<p>It is simple to show (reduce from $Partition$) there exists no $\alpha$-approximation for Bin Packing, for any $\alpha&lt;\frac{3}{2}$, unless $P=NP$.</p>

<p>That said, <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.45.7862&amp;rep=rep1&amp;type=pdf">Crescenzi et al.</a> have shown that unless the polynomial hierarchy collapses, Bin Packing is <strong>not</strong> APX-Hard.</p>

<p>As for (2), perhaps you could phrase it as "Does not admit $PTAS$ unless $P=NP$".</p>

CC BY-SA 3.0
2014-12-15T11:04:54.213Z
@cs_student_273 - you are welcome.
R B
CC BY-SA 3.0
2014-12-14T17:45:11.677Z
2014-12-14T17:45:11.677Z
R B
<p>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$.</p>

<p>1) Does this imply that the problem is $APX$-hard as well? </p>

<p>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"?</p>

<p>Thank you!</p>

<cc.complexity-theory><np-hardness><approximation-hardness><apx>
Does $NP$-hardness of $c$-approximation (for some $c>1$) imply $APX$-hardness?
cs_student_273
# Does $NP$-hardness of $c$-approximation (for some $c>1$) imply $APX$-hardness?

(Asked by: username_0 on 2014-12-14)

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!

**Tags:** cc.complexity-theory, np-hardness, approximation-hardness, apx

---

## 1 answers

### Answer by username_1 on 2014-12-14. Score: 12 | Accepted 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.](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.45.7862&rep=rep1&type=pdf) 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$".

> **Comments:**
> **username_1**: @cs_student_273 - you are welcome.  

---

