if it can be proven that the solution that the algorithm finds is at most a multiplicative factor of
For maximization problems, where an inferior solution has a smaller score,
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.
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: 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.
Unless P = NP, there exist problems in APX that are neither in PTAS nor APX-complete.
One other example of a potentially APX-intermediate problem is min edge coloring.
-APX contains problems with a polynomial time approximation algorithm with a
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.