APX

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.

n if it can be proven that the solution that the algorithm finds is at most a multiplicative factor of f(n) is a constant. The approximation ratio is conventionally stated greater than 1. In the case of minimization problems, 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) 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.

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.

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.

f(n)-APX, where 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 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

edit

• 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

edit