APX — Mediated Wiki

In computational 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.

== Definition == 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 ('''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 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.

== 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-reductions, which imply PTAS reductions.

=== Examples ===

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

* 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). * Min vertex cover. The complement of any maximal independent set must be a vertex cover. * Min dominating set in bounded-degree graphs. * The travelling salesman problem when the distances in the graph satisfy the conditions of a metric. TSP is 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, 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 <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 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 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.

== 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 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 }}.

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