12
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ A proof of such a theorem would likely resemble 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)$. $\endgroup$ Nov 22, 2011 at 0:23
  • 1
    $\begingroup$ $O(\log n)$ and $poly(n)$ are not constants. $\endgroup$ Nov 22, 2011 at 1:16
  • 2
    $\begingroup$ @TysonWilliams: I think he meant that in between PTAS and no approximation there are constants, log and poly(n) etc $\endgroup$ Nov 22, 2011 at 3:42
  • 6
    $\begingroup$ 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}$ ? $\endgroup$ Nov 22, 2011 at 3:44
  • 1
    $\begingroup$ 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) $\endgroup$
    – Gopi
    Nov 22, 2011 at 10:40

2 Answers 2

3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$

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.