# APX > Mediated Wiki article. Canonical URL: https://mediated.wiki/source/APX > Markdown URL: https://mediated.wiki/source/APX.md > Source: https://en.wikipedia.org/wiki/APX > Source revision: 1352639057 > License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/) {{Short description|Complexity class of approximable problems}} {{other uses}} In [computational complexity theory](/source/computational_complexity_theory), the class '''APX''' (an abbreviation of "approximable") is the set of '''[NP](/source/NP_(complexity))''' [optimization problem](/source/optimization_problem)s that allow [polynomial-time](/source/polynomial-time) [approximation algorithm](/source/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](/source/algorithm)s that can find an answer within some fixed multiplicative factor of the optimal answer. == Definition == An approximation algorithm is called an f(n)-approximation algorithm for input size n if it can be proven that the solution that the algorithm finds is at most a multiplicative factor of f(n) times worse than the optimal solution. Here, f(n) is called the ''approximation ratio''. '''Problems in APX''' are those with algorithms for which the approximation ratio f(n) is a constant c. The approximation ratio is conventionally stated greater than 1. In the case of minimization problems, f(n) 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, f(n) is sometimes stated as less than 1; in such cases, the reciprocal of f(n) 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 ('''PTAS''')](/source/Polynomial-time_approximation_scheme) 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](/source/P_%3D_NP_problem) 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 [knapsack problem](/source/knapsack_problem). == APX-hardness and APX-completeness == A problem is said to be '''APX-hard''' if there is a [PTAS reduction](/source/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](/source/L-reduction)s, which imply PTAS reductions. === Examples === One of the simplest APX-complete problems is [MAX-3SAT](/source/MAX-3SAT), a variation of the [Boolean satisfiability problem](/source/Boolean_satisfiability_problem). In this problem, we have a Boolean formula in [conjunctive normal form](/source/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: * [Max independent set](/source/Independent_set_(graph_theory)) 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). * [Min vertex cover](/source/Vertex_cover). The complement of any maximal independent set must be a vertex cover. * [Min dominating set](/source/Dominating_set) in bounded-degree graphs. * The [travelling salesman problem](/source/Travelling_salesman_problem) when the distances in the graph satisfy the conditions of a [metric](/source/Metric_(mathematics)). TSP is [NPO-complete](/source/Combinatorial_optimization) in the general case. * The [token reconfiguration](/source/token_reconfiguration) problem, via [L-reduction](/source/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](/source/P_%3D_NP_problem), 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](/source/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](/source/Edge_coloring). === f(n)-APX === One can also define a family of complexity classes f(n)-APX, where f(n)-APX contains problems with a polynomial time approximation algorithm with a O(f(n)) approximation ratio. One can analogously define f(n)-APX-complete classes; some such classes contain well-known optimization problems. Log-APX-completeness and poly-APX-completeness are defined in terms of [AP-reductions](/source/Approximation-preserving_reduction) 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 [min dominating set](/source/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](/source/Independent_set_(graph_theory)) 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](/source/Approximation-preserving_reduction) * [Complexity class](/source/Complexity_class) * [Approximation algorithm](/source/Approximation_algorithm) * [Max/min CSP/Ones classification theorems](/source/Max%2Fmin_CSP%2FOnes_classification_theorems) - a set of theorems that enable mechanical classification of problems about Boolean relations into approximability complexity classes * [MaxSNP](/source/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](/source/Marek_Karpinski) and [Gerhard Woeginger](/source/Gerhard_J._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 --- Adapted from the Wikipedia article [APX](https://en.wikipedia.org/wiki/APX) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/APX?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.