1
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Sep 5 '17 at 7:54
  • $\begingroup$ @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? $\endgroup$ – Stupid_Guy Sep 5 '17 at 15:57
2
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – Stupid_Guy Sep 5 '17 at 17:25
  • 2
    $\begingroup$ 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 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. $\endgroup$ – Sasho Nikolov Sep 5 '17 at 17:51
2
$\begingroup$

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, 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).

$\endgroup$

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.