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

CC BY-SA 4.0
2020-12-08T08:37:12.323Z
Your reasoning is correct, but the question will probably be closed anyway, as it is not research-level.
Jan Johannsen
CC BY-SA 4.0
2022-04-21T18:56:05.887Z
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: https://cs.stackexchange.com/questions/12112/are-there-any-problems-in-apx-ptas-that-are-not-apx-complete
EXPTIME-complete
<complexity-classes><approximation>
Is it to solid to conclude APX-complete after showing a problem cannot be approximated better than 1.5 and also develop a 2-approximation algorithm
Wenkai
# Is it to solid to conclude APX-complete after showing a problem cannot be approximated better than 1.5 and also develop a 2-approximation algorithm

(Asked by: username_0 on 2020-12-07)

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

**Tags:** complexity-classes, approximation
> **Comments:**
> **username_1**: Your reasoning is correct, but the question will probably be closed anyway, as it is not research-level.  
> **username_2**: 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: https://cs.stackexchange.com/questions/12112/are-there-any-problems-in-apx-ptas-that-are-not-apx-complete  

---

## 0 answers

