<p>Both statements seem to be false.</p>

<ol>
<li><p>Consider all Boolean formulas $\Phi$ in 3-CNF. The objective value of an $n$-variable formula $\Phi$ is $1/n$ if $\Phi$ is satisfiable, and is $1$ if $\Phi$ is not satisfiable. The corresponding minimization problem has an asymptotic PTAS (it is easy to come within an additive $+1$), but is not in APX (as this would allow you to solve 3-SAT).</p></li>
<li><p>Consider all undirected graphs. The objective value of a graph $G$ is its edge-chromatic number $\chi'(G)$. Holyer has proved that deciding $\chi'(G)=3$ is NP-hard. The corresponding minimization problem is APX-hard (there is no approximation algorithm with worst case ratio better than $4/3$), but the problem has an asymptotic PTAS (Vizing's theorem tells us that $\chi'(G)$ is between the max-degree and the max-degree plus 1).</p></li>
</ol>

CC BY-SA 3.0
2017-09-05T17:25:15.713Z
Thanks! The two examples are very nice. But one issue is that in the two examples $OPT(I)$ does not scale with the size of problem instance $I$?
zxzx179
CC BY-SA 3.0
2017-09-05T17:51:45.903Z
APX-hard means that there is a PTAS reduction from every problem in APX to this problem. This is not the same as NP-hard to approximate better than some constant, and minimum edge coloring is not known to be APX-hard: it is APX-Intermediate unless the polynomial hierarchy collapses, by Thm 4.10 in http://epubs.siam.org/doi/abs/10.1137/S0097539796304220. If I am parsing the proof of that theorem correctly, I think it actually holds for any problem with an asymptotic PTAS.
Sasho Nikolov
CC BY-SA 3.0
2017-09-05T17:16:44.920Z
2017-09-05T17:16:44.920Z
Gamow
<p>I think one issue is that we need to fix the "scale" of the problem. For example, the paper I refer to below defines NPO so that the objective function takes only positive integer values. With that definition, 1. is easy: fix say $\varepsilon = 1$, and then you get a $\max\{N_\varepsilon, 2\}$ approximation by definition.</p>

<p>With this definition of NPO, 2. also holds. In particular, no APX-Complete problem has an asymptotic PTAS unless the polynomial hierarchy collapses. See the remark on the bottom of page 1761 of <a href="http://epubs.siam.org/doi/abs/10.1137/S0097539796304220" rel="nofollow noreferrer">this paper</a>, and also the proof of Theorem 4.10. On a high level, the proof shows that if a problem has an asymptotic PTAS, then it can be approximated to any degree with a constant number of queries to an NP oracle (Proposition 4.6). On the other hand, any problem $P$ which can be computed with $k$ queries to an NP oracle can be reduced to approximating an instance of an APX-Complete problem $A$ within factor $r$, where $r$ is a constant depending on $k$ (Prop. 4.8). So, if you have an APX-Complete problem which has an asymptotic PTAS, then there is some constant $h$ so that the query hierarchy collapses to level $h$, i.e. any problem solvable with $k$ queries to NP, for any integer $k &gt; 0$, can be solved with $h$ queries to NP, where $h$ is a fixed constant which does not depend on $k$. This implies that the polynomial hierarchy collapses as well (Thm 4.2).</p>

CC BY-SA 3.0
2017-09-05T22:07:07.807Z
Thanks! I found this paper http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.159.2135&rep=rep1&type=pdf also verified these, under the assumption that objective takes integral values.
zxzx179
CC BY-SA 3.0
2017-09-05T18:24:18.597Z
2017-09-05T18:24:18.597Z
Sasho Nikolov
<p>The definition of asymptotic polynomial-time approximation scheme (Asymptotic PTAS) is defined as follows:</p>

<blockquote>
  <p>A minimization problem $\Pi$ is Asymptotic PTAS if for all $\epsilon$ there exists an algorithm $A_\epsilon$ and $N_\epsilon &gt; 0$, such that $A_\epsilon(I) \leq (1+\epsilon)OPT$ for $OPT(I) \geq N_\epsilon$.</p>
</blockquote>

<p>I have two questions:</p>

<ol>
<li>Is Asymptotic PTAS contained in APX?</li>
<li>If problem $\Pi$ is APX-Hard, does it imply that $\Pi$ is not Asymptotic PTAS (suppose $P \neq NP$)?</li>
</ol>

<p>I know above are true if we replace Asymptotic PTAS with PTAS (which are common-sense now). But I can't figure out how the definitions of Asymptotic PTAS and APX give answers to above questions.. </p>

CC BY-SA 3.0
2017-09-05T07:54:25.137Z
You can't say much with this definition alone because you can come up with optimization problems for which OPT($I$) is bounded for all inputs $I$. This makes the definition of an asymptotic PTAS vacuous. If, however, you define an optimization problem so that the maximum of OPT($I$) over all inputs $I$ of size $n$ goes to infinity with $n$, then it's easy to show that an asymptotic PTAS implies containment in APX.
Sasho Nikolov
CC BY-SA 3.0
2017-09-05T15:57:20.193Z
@SashoNikolov Thanks so much for your explanation! I think I understand this. So I guess for 2 it is also true, because we can solve all small instances within (albeit huge) constant time?
zxzx179
<cc.complexity-theory><np-hardness><complexity-classes><approximation-hardness>
Is Asymptotic PTAS $\subseteq$ APX?
zxzx179
# Is Asymptotic PTAS $\subseteq$ APX?

(Asked by: username_0 on 2017-09-05)

The definition of asymptotic polynomial-time approximation scheme (Asymptotic PTAS) is defined as follows:

> A minimization problem $\Pi$ is Asymptotic PTAS if for all $\epsilon$ there exists an algorithm $A\_\epsilon$ and $N\_\epsilon > 0$, such that $A\_\epsilon(I) \leq (1+\epsilon)OPT$ for $OPT(I) \geq N\_\epsilon$.

I have two questions:

1. Is Asymptotic PTAS contained in APX?
2. If problem $\Pi$ is APX-Hard, does it imply that $\Pi$ is not Asymptotic PTAS (suppose $P \neq NP$)?

I know above are true if we replace Asymptotic PTAS with PTAS (which are common-sense now). But I can't figure out how the definitions of Asymptotic PTAS and APX give answers to above questions..

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

> **Comments:**
> **username_1**: You can't say much with this definition alone because you can come up with optimization problems for which OPT($I$) is bounded for all inputs $I$. This makes the definition of an asymptotic PTAS vacuous. If, however, you define an optimization problem so that the maximum of OPT($I$) over all inputs $I$ of size $n$ goes to infinity with $n$, then it's easy to show that an asymptotic PTAS implies containment in APX.  
> **username_0**: @SashoNikolov Thanks so much for your explanation! I think I understand this. So I guess for 2 it is also true, because we can solve all small instances within (albeit huge) constant time?  

---

## 2 answers

### Answer by username_2 on 2017-09-05. Score: 2

Both statements seem to be false.

1. Consider all Boolean formulas $\Phi$ in 3-CNF. The objective value of an $n$-variable formula $\Phi$ is $1/n$ if $\Phi$ is satisfiable, and is $1$ if $\Phi$ is not satisfiable. The corresponding minimization problem has an asymptotic PTAS (it is easy to come within an additive $+1$), but is not in APX (as this would allow you to solve 3-SAT).
2. Consider all undirected graphs. The objective value of a graph $G$ is its edge-chromatic number $\chi'(G)$. Holyer has proved that deciding $\chi'(G)=3$ is NP-hard. The corresponding minimization problem is APX-hard (there is no approximation algorithm with worst case ratio better than $4/3$), but the problem has an asymptotic PTAS (Vizing's theorem tells us that $\chi'(G)$ is between the max-degree and the max-degree plus 1).

> **Comments:**
> **username_0**: Thanks! The two examples are very nice. But one issue is that in the two examples $OPT(I)$ does not scale with the size of problem instance $I$?  
> **username_1**: APX-hard means that there is a PTAS reduction from every problem in APX to this problem. This is not the same as NP-hard to approximate better than some constant, and minimum edge coloring is not known to be APX-hard: it is APX-Intermediate unless the polynomial hierarchy collapses, by Thm 4.10 in http://epubs.siam.org/doi/abs/10.1137/S0097539796304220. If I am parsing the proof of that theorem correctly, I think it actually holds for any problem with an asymptotic PTAS.  

---

### Answer by username_1 on 2017-09-05. Score: 2

I think one issue is that we need to fix the "scale" of the problem. For example, the paper I refer to below defines NPO so that the objective function takes only positive integer values. With that definition, 1. is easy: fix say $\varepsilon = 1$, and then you get a $\max\{N\_\varepsilon, 2\}$ approximation by definition.

With this definition of NPO, 2. also holds. In particular, no APX-Complete problem has an asymptotic PTAS unless the polynomial hierarchy collapses. See the remark on the bottom of page 1761 of [this paper](http://epubs.siam.org/doi/abs/10.1137/S0097539796304220), and also the proof of Theorem 4.10. On a high level, the proof shows that if a problem has an asymptotic PTAS, then it can be approximated to any degree with a constant number of queries to an NP oracle (Proposition 4.6). On the other hand, any problem $P$ which can be computed with $k$ queries to an NP oracle can be reduced to approximating an instance of an APX-Complete problem $A$ within factor $r$, where $r$ is a constant depending on $k$ (Prop. 4.8). So, if you have an APX-Complete problem which has an asymptotic PTAS, then there is some constant $h$ so that the query hierarchy collapses to level $h$, i.e. any problem solvable with $k$ queries to NP, for any integer $k > 0$, can be solved with $h$ queries to NP, where $h$ is a fixed constant which does not depend on $k$. This implies that the polynomial hierarchy collapses as well (Thm 4.2).

> **Comments:**
> **username_0**: Thanks! I found this paper http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.159.2135&rep=rep1&type=pdf also verified these, under the assumption that objective takes integral values.  

---

