APX

Short description: Complexity class of approximable problems

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.

An approximation algorithm is called an [math]\displaystyle{ f(n) }[/math]-approximation algorithm for input size [math]\displaystyle{ n }[/math] if it can be proven that the solution that the algorithm finds is at most a multiplicative factor of [math]\displaystyle{ f(n) }[/math] times worse than the optimal solution. Here, [math]\displaystyle{ f(n) }[/math] is called the approximation ratio. Problems in APX are those with algorithms for which the approximation ratio [math]\displaystyle{ f(n) }[/math] is a constant [math]\displaystyle{ c }[/math]. The approximation ratio is conventionally stated greater than 1. In the case of minimization problems, [math]\displaystyle{ 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]\displaystyle{ f(n) }[/math] is sometimes stated as less than 1; in such cases, the reciprocal of [math]\displaystyle{ 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 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, 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-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:

• 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

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]\displaystyle{ f(n) }[/math]-APX, where [math]\displaystyle{ f(n) }[/math]-APX contains problems with a polynomial time approximation algorithm with a [math]\displaystyle{ O(f(n)) }[/math] approximation ratio. One can analogously define [math]\displaystyle{ 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

• Complexity Zoo: APX
• C. Papadimitriou and M. Yannakakis. 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. Maximum Satisfiability . A compendium of NP optimization problems .