I know the canonical way to show APX-Complete is to give an L-reduction from an already-known APX-complete problem. If I have used gap-preserving reduction to show a problem cannot be approximated better than 1.5 unless P=NP. On the other hand, I have also developed an algorithm to approximate this problem by 2. Actually, I use the relaxed LP to solve the problem, and a rounding method could lead to a 2-approximation. I'd like to know if it is enough to conclude this problem is APX-hard and APX-complete. Because gap-preserving reduction shows it is at least APX-hard, which does not allow PTAS, and meanwhile, my 2-approximation proves it can be approximated by a constant. Is it enough to draw an APX-complete conclusion directly without additional giving an L-reduction? Thanks a lot for your explanation

  • 1
    $\begingroup$ Your reasoning is correct, but the question will probably be closed anyway, as it is not research-level. $\endgroup$ Dec 8, 2020 at 8:37
  • $\begingroup$ Showing that the problem cannot be 1.5-approximated unless P=NP proves that it cannot belong to PTAS unless P=NP, but the problem could still turn out to be APX-intermediate ---and thus, not APX-hard. See this question: cs.stackexchange.com/questions/12112/… $\endgroup$ Apr 21 at 18:56


Your Answer

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

Browse other questions tagged or ask your own question.