HOME

TheInfoList



OR:

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 In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by t ...
approximation algorithm In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned sol ...
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 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 f(n)-approximation algorithm for input size n if it can be proven that the solution that the algorithm finds is at most a multiplicative factor of f(n) times worse than the optimal solution. Here, f(n) is called the ''approximation ratio''. Problems in APX are those with algorithms for which the approximation ratio f(n) is a constant c. The approximation ratio is conventionally stated greater than 1. In the case of minimization problems, f(n) 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, f(n) is sometimes stated as less than 1; in such cases, the reciprocal of 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 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 appro ...
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-pres ...
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 satisf ...
. 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 mathe ...
. 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-pres ...
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 f(n)-APX, where f(n)-APX contains problems with a polynomial time approximation algorithm with a O(f(n)) approximation ratio. One can analogously define 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

*
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 of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory. In general, a complexity class is defined in terms o ...
*
Approximation algorithm In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned sol ...
*
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,
Marek Karpinski Marek KarpinskiMarek Karpinski Biography
at the Hausdorff Center for Mathematics, Exc ...
and
Gerhard Woeginger Gerhard J. Woeginger (31 May 1964 – 1 April 2022) was an Austrian mathematician and computer scientist who worked in Germany as a professor at RWTH Aachen University, where he chaired the algorithms and complexity group in the department of co ...

Maximum Satisfiability

''A compendium of NP optimization problems''
. {{DEFAULTSORT:APX Complexity classes Approximation algorithms