APX
Encyclopedia
In complexity theory
the class APX (an abbreviation of "approximable") is the set of NP optimization problems 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 percentage of the optimal answer. For example, there is a polynomial-time algorithm which will find a solution to the bin packing problem
that uses at most 5% more than the smallest possible number of bins.
An approximation algorithm is called a c-approximation algorithm for some constant c if it can be proven that the solution that the algorithm finds is at most c times worse than the optimal solution. Here, c is called the approximation ratio. Depending on whether the problem is a minimization or a maximization problem, this can either denote c times larger or c times smaller, respectively. For example, the vertex cover problem and traveling salesman problem with triangle inequality each have simple 2-approximation algorithms. In contrast, it's proven that the traveling salesman problem with arbitrary edge-lengths can not be approximated with approximation ratio bounded by a constant as long as the Hamiltonian-path problem can not be solved in polynomial time.
If there is a polynomial-time algorithm to solve a problem within every fixed percentage greater than zero (one algorithm for each percentage), then the problem is said to have a polynomial-time approximation scheme
(PTAS). Unless P=NP, it can be shown that there are problems that are in APX but not in PTAS; that is, problems that can be approximated within some constant factor, but not every constant factor. 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, P ≠ NP ⇒ no APX-hard problem is in PTAS.
To say a problem is APX-hard is generally bad news, because if P ≠ NP, it denies the existence of a PTAS, which is the most useful sort of approximation algorithm. One of the simplest APX-complete problems is the maximum satisfiability problem
, a variation of the boolean satisfiability problem
. In this problem, we have a boolean formula in conjunctive normal form
, 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. Despite the fact that it probably does not have a PTAS, however, the correct answer can still be estimated within 30%, and some simplified variants do have a PTAS.
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
the class APX (an abbreviation of "approximable") is the set of NP optimization problems that allow polynomial-time approximation algorithm
Approximation algorithm
In computer science and operations research, approximation algorithms are algorithms used to find approximate solutions to optimization problems. Approximation algorithms are often associated with NP-hard problems; since it is unlikely that there can ever be efficient polynomial time exact...
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
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
s that can find an answer within some fixed percentage of the optimal answer. For example, there is a polynomial-time algorithm which will find a solution to the bin packing problem
Bin packing problem
In computational complexity theory, the bin packing problem is a combinatorial NP-hard problem. In it, objects of different volumes must be packed into a finite number of bins of capacity V in a way that minimizes the number of bins used....
that uses at most 5% more than the smallest possible number of bins.
An approximation algorithm is called a c-approximation algorithm for some constant c if it can be proven that the solution that the algorithm finds is at most c times worse than the optimal solution. Here, c is called the approximation ratio. Depending on whether the problem is a minimization or a maximization problem, this can either denote c times larger or c times smaller, respectively. For example, the vertex cover problem and traveling salesman problem with triangle inequality each have simple 2-approximation algorithms. In contrast, it's proven that the traveling salesman problem with arbitrary edge-lengths can not be approximated with approximation ratio bounded by a constant as long as the Hamiltonian-path problem can not be solved in polynomial time.
If there is a polynomial-time algorithm to solve a problem within every fixed percentage greater than zero (one algorithm for each percentage), then the problem is said to have a polynomial-time approximation scheme
Polynomial-time approximation scheme
In computer science, a polynomial-time approximation scheme is a type of approximation algorithm for optimization problems ....
(PTAS). Unless P=NP, it can be shown that there are problems that are in APX but not in PTAS; that is, problems that can be approximated within some constant factor, but not every constant factor. A problem is said to be APX-hard if there is a PTAS reduction
PTAS reduction
In computational complexity theory, a PTAS reduction is a reduction that is often used to perform reductions between solutions to optimization problems. It preserves the property that a problem has a polynomial time approximation scheme and is used to define completeness for certain classes of...
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, P ≠ NP ⇒ no APX-hard problem is in PTAS.
To say a problem is APX-hard is generally bad news, because if P ≠ NP, it denies the existence of a PTAS, which is the most useful sort of approximation algorithm. One of the simplest APX-complete problems is the maximum satisfiability problem
Maximum satisfiability problem
In computational complexity theory, the Maximum Satisfiability problem is the problem of determining the maximum number of clauses, of a given Boolean formula, that can be satisfied by some assignment...
, a variation of the boolean satisfiability problem
Boolean satisfiability problem
In computer science, satisfiability is the problem of determining if the variables of a given Boolean formula can be assigned in such a way as to make the formula evaluate to TRUE...
. In this problem, we have a boolean formula in conjunctive normal form
Conjunctive normal form
In Boolean logic, a formula is in conjunctive normal form if it is a conjunction of clauses, where a clause is a disjunction of literals.As a normal form, it is useful in automated theorem proving...
, 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. Despite the fact that it probably does not have a PTAS, however, the correct answer can still be estimated within 30%, and some simplified variants do have a PTAS.