8
$\begingroup$

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!

$\endgroup$
12
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.