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$ – Jan Johannsen Dec 8 '20 at 8:37

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.