In complexity theory the class APX (an abbreviation of "approximable") is the set of NP optimization problems that allow polynomial-time approximation algorithms with approximation ratio bounded by a constant (or constant-factor approximation algorithms for short). In simple terms, problems in this class have efficient algorithms that can find an answer within some fixed multiplicative factor of the optimal answer.
Contents
An approximation algorithm is called a
If there is a polynomial-time algorithm to solve a problem to within every multiplicative factor of the optimum other than 1, then the problem is said to have a polynomial-time approximation scheme (PTAS). Unless P=NP there exist problems that are in APX but without a PTAS, so the class of problems with a PTAS is strictly contained in APX. One such problem is the bin packing problem.
APX-Hardness and APX-Completeness
A problem is said to be APX-hard if there is a PTAS reduction from every problem in APX to that problem, and to be APX-complete if the problem is APX-hard and also in APX. As a consequence of P ≠ NP ⇒ PTAS ≠ APX, the fact P ≠ NP implies that no APX-hard problem has a PTAS. In practice, reducing one problem to another to demonstrate APX-completeness is often done using other reduction schemes, such as L-reductions, which imply PTAS reductions.
Examples
One of the simplest APX-complete problems is MAX-3SAT-3, a variation of the boolean satisfiability problem. In this problem, we have a boolean formula in conjunctive normal form where each variable appears at most 3 times, and we wish to know the maximum number of clauses that can be simultaneously satisfied by a single assignment of true/false values to the variables.
Other APX-complete problems include:
PTAS
PTAS (Polynomial Time Approximation Scheme) consists of problems that can be approximated to within any constant factor besides 1 in time that is polynomial to the input size, but the polynomial depends on such factor. This class is a subset of APX.
APX-Intermediate
Unless P = NP, there exist problems in APX that are neither in PTAS nor APX-complete. Such problems can be thought of as having a hardness between PTAS problems and APX-complete problems, and may be called APX-intermediate. The bin packing problem is thought to be APX-intermediate. Despite not having a known PTAS, the bin packing problem has several "asymptotic PTAS" algorithms, which behave like a PTAS when the optimum solution is large, so intuitively it may be easier than problems that are APX-hard.
One other example of a potentially APX-intermediate problem is Min Edge Coloring.
f(n)-APX
One can also define a family of complexity classes
Log-APX-complete, consisting of the hardest problems that can be approximated efficiently to within a factor logarithmic in the input size, includes Min Dominating Set when degree is unbounded.
Poly-APX-complete, consisting of the hardest problems that can be approximated efficiently to within a factor polynomial in the input size, includes Max Independent Set in the general case.
There also exist problems that are Exp-APX-complete, where the approximation ratio is exponential in the input size. This may occur when the approximation is dependent on the value of numbers within the problem instance; these numbers may be expressed in space logarithmic in their value, hence the exponential factor.