View source for APX

{{Short description|Complexity class of approximable problems}}
{{other uses}}

In [[computational complexity theory]], the class '''APX''' (an abbreviation of "approximable") is the set of '''[[NP (complexity)|NP]]''' [[optimization problem]]s that allow [[polynomial-time]] [[approximation algorithm]]s with approximation ratio bounded by a constant (or '''constant-factor approximation algorithms''' for short). In simple terms, problems in this class have efficient [[algorithm]]s that can find an answer within some fixed multiplicative factor of the optimal answer.

An approximation algorithm is called an <math>f(n)</math>-approximation algorithm for input size <math>n</math> if it can be proven that the solution that the algorithm finds is at most a multiplicative factor of <math>f(n)</math> times worse than the optimal solution. Here, <math>f(n)</math> is called the ''approximation ratio''. Problems in APX are those with algorithms for which the approximation ratio <math>f(n)</math> is a constant <math>c</math>. The approximation ratio is conventionally stated greater than 1. In the case of minimization problems, <math>f(n)</math> is the found solution's score divided by the optimum solution's score, while for maximization problems the reverse is the case. For maximization problems, where an inferior solution has a smaller score, <math>f(n)</math> is sometimes stated as less than 1; in such cases, the reciprocal of <math>f(n)</math> is the ratio of the score of the found solution to the score of the optimum solution.

A problem is said to have a [[Polynomial-time approximation scheme|polynomial-time approximation scheme ('''PTAS''')]] if for ''every'' multiplicative factor of the optimum worse than 1 there is a polynomial-time algorithm to solve the problem to within that factor. Unless [[P = NP problem|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 example of a problem with a PTAS 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, if P ≠ NP is assumed, 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-reduction]]s, which imply PTAS reductions.

=== Examples ===

One of the simplest APX-complete problems is [[MAX-3SAT|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:

* [[Independent set (graph theory)#Approximation algorithms|Max independent set]] in bounded-degree graphs (here, the approximation ratio depends on the maximum degree of the graph, but is constant if the max degree is fixed).
* [[Vertex cover#Approximate evaluation|Min vertex cover]]. The complement of any maximal independent set must be a vertex cover.
* [[Dominating set#Algorithms and computational complexity|Min dominating set]] in bounded-degree graphs.
* The [[Travelling salesman problem#Complexity of approximation|travelling salesman problem]] when the distances in the graph satisfy the conditions of a [[Metric (mathematics)|metric]]. TSP is [[Combinatorial_optimization#NP_optimization_problem|NPO-complete]] in the general case.
* The [[token reconfiguration]] problem, via [[L-reduction]] from set cover.

== Related complexity classes ==

=== PTAS ===
{{Main|Polynomial-time approximation scheme}}

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 problem|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 [[Edge coloring#Algorithms that use more than the optimal number of colors|min edge coloring]].

=== f(n)-APX ===

One can also define a family of complexity classes <math>f(n)</math>-APX, where <math>f(n)</math>-APX contains problems with a polynomial time approximation algorithm with a <math>O(f(n))</math> approximation ratio. One can analogously define <math>f(n)</math>-APX-complete classes; some such classes contain well-known optimization problems. Log-APX-completeness and poly-APX-completeness are defined in terms of [[Approximation-preserving reduction#AP-reduction|AP-reductions]] rather than PTAS-reductions; this is because PTAS-reductions are not strong enough to preserve membership in Log-APX and Poly-APX, even though they suffice for APX.

Log-APX-complete, consisting of the hardest problems that can be approximated efficiently to within a factor logarithmic in the input size, includes [[Dominating set#Algorithms and computational complexity|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 [[Independent set (graph theory)#Approximation algorithms|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.

== See also ==
* [[Approximation-preserving reduction]]
* [[Complexity class]]
* [[Approximation algorithm]]
* [[Max/min CSP/Ones classification theorems]] - a set of theorems that enable mechanical classification of problems about Boolean relations into approximability complexity classes
* [[MaxSNP]] - a closely related subclass

== References ==

* {{CZoo|APX|A#apx}}
* C. Papadimitriou and M. Yannakakis. [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.89.3995&rep=rep1&type=pdf Optimization, approximation and complexity classes]. Journal of Computer and System Sciences, 43:425–440, 1991.
* Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, [[Marek Karpinski]] and [[Gerhard J. Woeginger|Gerhard Woeginger]]. [https://www.csc.kth.se/~viggo/wwwcompendium/node225.html Maximum Satisfiability] {{Webarchive|url=https://web.archive.org/web/20070413152307/https://www.csc.kth.se/~viggo/wwwcompendium/node225.html |date=2007-04-13 }}. [https://www.csc.kth.se/%7Eviggo/wwwcompendium/ ''A compendium of NP optimization problems''] {{Webarchive|url=https://web.archive.org/web/20070405050438/https://www.csc.kth.se/~viggo/wwwcompendium/ |date=2007-04-05 }}.

{{ComplexityClasses}}

{{DEFAULTSORT:APX}}
[[Category:Complexity classes]]
[[Category:Approximation algorithms]]