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

Improve this question
$\endgroup$
2
  • 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, 2017 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$
    – zxzx179
    Sep 5, 2017 at 15:57

2 Answers 2

Reset to default
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).

Improve this answer
$\endgroup$
2
  • $\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$
    – zxzx179
    Sep 5, 2017 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, 2017 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).

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks! I found this paper citeseerx.ist.psu.edu/viewdoc/… also verified these, under the assumption that objective takes integral values. $\endgroup$
    – zxzx179
    Sep 5, 2017 at 22:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.