Hierarchy theorem for approximation ratios?

Question

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$?

Answer 1

There is an approximation hierarchy, the main known examples: FPTAS $\subseteq$ EPTAS $\subseteq$ PTAS $\subseteq$ APX. But for inapproximability there also is NPO-PB.

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 because it has many more information and references on those examples, even Wikipedia

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