In
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved ...
, the class APX (an abbreviation of "approximable") is the set of
NP optimization problem
In mathematics, computer science and economics, an optimization problem is the problem of finding the ''best'' solution from all feasible solutions.
Optimization problems can be divided into two categories, depending on whether the variables ...
s 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
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
s that can find an answer within some fixed multiplicative factor of the optimal answer.
An approximation algorithm is called an
-approximation algorithm for input size
if it can be proven that the solution that the algorithm finds is at most a multiplicative factor of
times worse than the optimal solution. Here,
is called the ''approximation ratio''. Problems in APX are those with algorithms for which the approximation ratio
is a constant
. The approximation ratio is conventionally stated greater than 1. In the case of minimization problems,
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,
is sometimes stated as less than 1; in such cases, the reciprocal of
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
The P versus NP problem is a major unsolved problem in theoretical computer science. In informal terms, it asks whether every problem whose solution can be quickly verified can also be quickly solved.
The informal term ''quickly'', used above ...
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
The bin packing problem is an optimization problem, in which items of different sizes must be packed into a finite number of bins or containers, each of a fixed given capacity, in a way that minimizes the number of bins used. The problem has ma ...
.
APX-hardness and APX-completeness
A problem is said to be APX-hard if there is a
PTAS reduction In computational complexity theory, a PTAS reduction is an approximation-preserving reduction that is often used to perform reductions between solutions to optimization problems. It preserves the property that a problem has a polynomial time approx ...
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 In computer science, particularly the study of approximation algorithms, an
L-reduction ("''linear reduction''") is a transformation of optimization problems which linearly preserves approximability features; it is one type of approximation-preser ...
s, which imply PTAS reductions.
Examples
One of the simplest APX-complete problems is
MAX-3SAT-3, a variation of the
boolean satisfiability problem
In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) is the problem of determining if there exists an interpretation that satisfie ...
. In this problem, we have a boolean formula in
conjunctive normal form
In Boolean logic, a formula is in conjunctive normal form (CNF) or clausal normal form if it is a conjunction of one or more clauses, where a clause is a disjunction of literals; otherwise put, it is a product of sums or an AND of ORs. As a cano ...
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
The travelling salesman problem (also called the travelling salesperson problem or TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each cit ...
when the distances in the graph satisfy the conditions of a
metric
Metric or metrical may refer to:
* Metric system, an internationally adopted decimal system of measurement
* An adjective indicating relation to measurement in general, or a noun describing a specific type of measurement
Mathematics
In mathem ...
. TSP is
NPO-complete in the general case.
* The
token reconfiguration In computational complexity theory and combinatorics, the token reconfiguration problem is a reconfiguration problem on a graph with both an initial and desired state for tokens.
Given a graph G, an initial state of tokens is defined by a subset V ...
problem, via
L-reduction In computer science, particularly the study of approximation algorithms, an
L-reduction ("''linear reduction''") is a transformation of optimization problems which linearly preserves approximability features; it is one type of approximation-preser ...
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
The P versus NP problem is a major unsolved problem in theoretical computer science. In informal terms, it asks whether every problem whose solution can be quickly verified can also be quickly solved.
The informal term ''quickly'', used above ...
, 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
The bin packing problem is an optimization problem, in which items of different sizes must be packed into a finite number of bins or containers, each of a fixed given capacity, in a way that minimizes the number of bins used. The problem has ma ...
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
-APX, where
-APX contains problems with a polynomial time approximation algorithm with a
approximation ratio. One can analogously define
-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
In computability theory and computational complexity theory, especially the study of approximation algorithms, an approximation-preserving reduction is an algorithm for transforming one optimization problem into another problem, such that the dista ...
*
Complexity class
In computational complexity theory, a complexity class is a set (mathematics), set of computational problems of related resource-based computational complexity, complexity. The two most commonly analyzed resources are time complexity, time and spa ...
*
Approximation algorithm
*
Max/min CSP/Ones classification theorems
In computational complexity theory, a branch of computer science, the Max/min CSP/Ones classification theorems state necessary and sufficient conditions that determine the complexity classes of problems about satisfying a subset ''S'' of boolean re ...
- a set of theorems that enable mechanical classification of problems about boolean relations into approximability complexity classes
*
MaxSNP In computational complexity theory, SNP (from Strict NP) is a complexity class containing a limited subset of NP based on its logical characterization in terms of graph-theoretical properties. It forms the basis for the definition of the class Ma ...
- a closely related subclass
References
*
* 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,
and
Gerhard WoegingerMaximum Satisfiability''A compendium of NP optimization problems''.
{{DEFAULTSORT:APX
Complexity classes
Approximation algorithms