<p>There is an approximation hierarchy, the main known examples: <a href="http://qwiki.stanford.edu/wiki/Complexity_Zoo%3aF#fptas" rel="nofollow">FPTAS</a> $\subseteq$ <a href="http://qwiki.stanford.edu/wiki/Complexity_Zoo%3aE#eptas" rel="nofollow">EPTAS</a> $\subseteq$ <a href="http://qwiki.stanford.edu/wiki/Complexity_Zoo%3aP#ptas" rel="nofollow">PTAS</a> $\subseteq$ <a href="http://qwiki.stanford.edu/wiki/Complexity_Zoo%3aA#apx" rel="nofollow">APX</a>. But for inapproximability there also is <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aN#npopb" rel="nofollow">NPO-PB</a>.</p>

<p>There are a lot of results about the set of possible ratios, going from results like this one: </p>

<blockquote>
  <p>$P||C_{max} \in$ EPTAS$\backslash$ FPTAS, unless $P=NP$, </p>
</blockquote>

<p>to defining APX/NPO-PB-hard problems.</p>

<p>Some references:</p>

<ul>
<li>ON PTAS: M. Cesati and L. Trevisan. On the efficiency of polynomial time approximation schemes, 1997. </li>
<li>On NPOPB: V. Kann. Strong lower bounds on the approximability of some NPO PB-complete maximization problems</li>
</ul>

<p>But I suggest the best will be to check the <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo" rel="nofollow">Complexity Zoo</a> because it has many more information and references on those examples, even <a href="http://en.wikipedia.org/wiki/Polynomial-time_approximation_scheme" rel="nofollow">Wikipedia</a></p>

<p>Furthermore, as stated in the comments the tight bound when $\alpha=O(1)$, was shown for many problems such as bin packing, machine scheduling (see iris.gmu.edu/~khoffman/papers/set_covering.html).</p>

CC BY-SA 3.0
2011-11-27T10:26:13.040Z
2011-11-27T10:26:13.040Z
Gopi
<p>I still think Suresh's comment below the question is enough to show that any ratio is possible. If you are not convinced with that, you can look at Boolean Constraint Satisfaction Problems (CSPs), for example.</p>

<p>Background: Let $P: \{0,1\}^k \to \{0,1\}$ be a predicate of arity $k$. An instance of Max-CSP(P) is over $n \gg k$ Boolean variables $x_1, \ldots, x_n$. A literal is any variable or its negation. The instance consists of $m$ constraints, each of the form $P(\lambda_1, \ldots, \lambda_k)$ where the $\lambda_i$ are some literals, and the goal is to find an assignment of the variables that maximizes the fraction of satisfies constraints. For example, in $3SAT$ we have $P(x_1, x_2, x_3) = x_1 \lor x_2 \lor x_3$. Define $\rho(P)$ as the fraction of $2^k$ possible inputs that satisfy $P$ (for $3SAT$ it is equal to $7/8$). It is trivial to approximate any Max-CSP(P) by a factor $\rho(P)$ by assigning random values to variables (and then derandimize using the method of conditional expectations). Note that here we have the convention that approximation ratios are positive reals no more than 1.  A predicate $P$ is Approximation Resistant (AR) if it is NP-hard to solve Max-CSP(P) better than by a factor $\rho(P)$ (i.e., $\rho(P)+\epsilon$ for any fixed $\epsilon > 0$).</p>

<p>Note that any AR predicate demonstrates a tight approximation threshold $\rho(P)$. It is known that there are predicates $P$ with arbitrarily small $\rho(P)$ that are approximation resistant, and remain so even if you add to the accepting inputs of $P$. For example, the following paper shows one such result:</p>

<p>Per Austrin and Johan Håstad, Randomly Supported Independence and Resistance, SIAM Journal on Computing, vol. 40, no. 1, pp. 1-27, 2011. </p>

<p>So this takes care of all rational thresholds whose denominator is a power of two. For other thresholds, observe that if suffices to show that for every $\alpha$, there is an $\alpha&#39; \leq \alpha$ for which there is an AR predicate with $\rho(P) = \alpha&#39;$ (since it is always possible to add dummy variables and constraints of them that are trivially satisfiable so as to increase the approximation threshold).</p>

CC BY-SA 3.0
2011-11-27T22:29:04.567Z
2011-11-28T19:24:50.780Z
2011-11-28T19:24:50.780Z
Mahdi Cheraghchi
<p>As is well known, NP-hard optimization problems can have many different approximation ratios, ranging all the way from having a PTAS to not being approximable within any factor. In between, we have various constants, $O(\log n)$, $poly(n)$, etc.</p>

<p>What is known about the set of possible ratios? Can we prove any sort of "approximation hierarchy"? Formally, for what functions $f(n)$ and $g(n)$ can we prove that there exists a problem with approximation ratio $f(n)\leq \alpha &lt; g(n)$?</p>

<p>In the case that $\alpha=O(1)$, does there exist a problem with approximation ratio exactly $\alpha$?</p>

CC BY-SA 3.0
2011-11-22T00:23:26.057Z
A proof of such a theorem would likely resemble http://www.wisdom.weizmann.ac.il/~oded/p_testHT.html. Given a problem with known approximation bound $\alpha$, we make the problem "easier" somehow, presumably using some form of padding, to get a problem with approximation bound $f(\alpha)$.
Jeremy Hurwitz
CC BY-SA 3.0
2011-11-22T01:16:26.757Z
$O(\log n)$ and $poly(n)$ are not constants.
Tyson Williams
CC BY-SA 3.0
2011-11-22T03:42:05.630Z
@TysonWilliams: I think he meant that in between PTAS and no approximation there are constants, log and poly(n) etc
Suresh Venkat
CC BY-SA 3.0
2011-11-22T03:44:24.940Z
Wouldn't you need to rule out trivial transformations where an $\alpha$-approximation for minimizing f immediately is a $\sqrt{\alpha}$ approximation for minimizing $\sqrt{f}$ ?
Suresh Venkat
CC BY-SA 3.0
2011-11-22T03:51:53.300Z
@Suresh Venkat Ah, yes.  I see it now.  Thanks.
Tyson Williams
CC BY-SA 3.0
2011-11-22T10:40:59.030Z
As for your last question about α=O(1), the tight bound has been shown for many problems such as bin packing, machine scheduling (iris.gmu.edu/~khoffman/papers/set_covering.html)
Gopi
<cc.complexity-theory><approximation-hardness>
Hierarchy theorem for approximation ratios?
Jeremy Hurwitz
# Hierarchy theorem for approximation ratios?

(Asked by: username_0 on 2011-11-22)

As is well known, NP-hard optimization problems can have many different approximation ratios, ranging all the way from having a PTAS to not being approximable within any factor. In between, we have various constants, $O(\log n)$, $poly(n)$, etc.

What is known about the set of possible ratios? Can we prove any sort of "approximation hierarchy"? Formally, for what functions $f(n)$ and $g(n)$ can we prove that there exists a problem with approximation ratio $f(n)\leq \alpha < g(n)$?

In the case that $\alpha=O(1)$, does there exist a problem with approximation ratio exactly $\alpha$?

**Tags:** cc.complexity-theory, approximation-hardness
> **Comments:**
> **username_0**: A proof of such a theorem would likely resemble http://www.wisdom.weizmann.ac.il/~oded/p_testHT.html. Given a problem with known approximation bound $\alpha$, we make the problem "easier" somehow, presumably using some form of padding, to get a problem with approximation bound $f(\alpha)$.  
> **username_1**: $O(\log n)$ and $poly(n)$ are not constants.  
> **username_2**: @TysonWilliams: I think he meant that in between PTAS and no approximation there are constants, log and poly(n) etc  
> **username_2**: Wouldn't you need to rule out trivial transformations where an $\alpha$-approximation for minimizing f immediately is a $\sqrt{\alpha}$ approximation for minimizing $\sqrt{f}$ ?  
> **username_1**: @Suresh Venkat Ah, yes.  I see it now.  Thanks.  
> **username_3**: As for your last question about α=O(1), the tight bound has been shown for many problems such as bin packing, machine scheduling (iris.gmu.edu/~khoffman/papers/set_covering.html)  

---

## 2 answers

### Answer by username_3 on 2011-11-27. Score: 3

There is an approximation hierarchy, the main known examples: [FPTAS](http://qwiki.stanford.edu/wiki/Complexity_Zoo%3aF#fptas) $\subseteq$ [EPTAS](http://qwiki.stanford.edu/wiki/Complexity_Zoo%3aE#eptas) $\subseteq$ [PTAS](http://qwiki.stanford.edu/wiki/Complexity_Zoo%3aP#ptas) $\subseteq$ [APX](http://qwiki.stanford.edu/wiki/Complexity_Zoo%3aA#apx). But for inapproximability there also is [NPO-PB](http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aN#npopb).

There are a lot of results about the set of possible ratios, going from results like this one:

> $P||C\_{max} \in$ EPTAS$\backslash$ FPTAS, unless $P=NP$,

to defining APX/NPO-PB-hard problems.

Some references:

* ON PTAS: M. Cesati and L. Trevisan. On the efficiency of polynomial time approximation schemes, 1997.
* On NPOPB: V. Kann. Strong lower bounds on the approximability of some NPO PB-complete maximization problems

But I suggest the best will be to check the [Complexity Zoo](http://qwiki.stanford.edu/index.php/Complexity_Zoo) because it has many more information and references on those examples, even [Wikipedia](http://en.wikipedia.org/wiki/Polynomial-time_approximation_scheme)

Furthermore, as stated in the comments the tight bound when $\alpha=O(1)$, was shown for many problems such as bin packing, machine scheduling (see iris.gmu.edu/~khoffman/papers/set\_covering.html).


---

### Answer by username_4 on 2011-11-27. Score: 2

I still think Suresh's comment below the question is enough to show that any ratio is possible. If you are not convinced with that, you can look at Boolean Constraint Satisfaction Problems (CSPs), for example.

Background: Let $P: \{0,1\}^k \to \{0,1\}$ be a predicate of arity $k$. An instance of Max-CSP(P) is over $n \gg k$ Boolean variables $x\_1, \ldots, x\_n$. A literal is any variable or its negation. The instance consists of $m$ constraints, each of the form $P(\lambda\_1, \ldots, \lambda\_k)$ where the $\lambda\_i$ are some literals, and the goal is to find an assignment of the variables that maximizes the fraction of satisfies constraints. For example, in $3SAT$ we have $P(x\_1, x\_2, x\_3) = x\_1 \lor x\_2 \lor x\_3$. Define $\rho(P)$ as the fraction of $2^k$ possible inputs that satisfy $P$ (for $3SAT$ it is equal to $7/8$). It is trivial to approximate any Max-CSP(P) by a factor $\rho(P)$ by assigning random values to variables (and then derandimize using the method of conditional expectations). Note that here we have the convention that approximation ratios are positive reals no more than 1. A predicate $P$ is Approximation Resistant (AR) if it is NP-hard to solve Max-CSP(P) better than by a factor $\rho(P)$ (i.e., $\rho(P)+\epsilon$ for any fixed $\epsilon > 0$).

Note that any AR predicate demonstrates a tight approximation threshold $\rho(P)$. It is known that there are predicates $P$ with arbitrarily small $\rho(P)$ that are approximation resistant, and remain so even if you add to the accepting inputs of $P$. For example, the following paper shows one such result:

Per Austrin and Johan Håstad, Randomly Supported Independence and Resistance, SIAM Journal on Computing, vol. 40, no. 1, pp. 1-27, 2011.

So this takes care of all rational thresholds whose denominator is a power of two. For other thresholds, observe that if suffices to show that for every $\alpha$, there is an $\alpha' \leq \alpha$ for which there is an AR predicate with $\rho(P) = \alpha'$ (since it is always possible to add dummy variables and constraints of them that are trivially satisfiable so as to increase the approximation threshold).


---

