APX

<h2 id="apx-hardness-and-apx-completeness">APX-hardness and APX-completeness</h2>
<p>A problem is said to be APX-hard if there is a <a href="/facts/PTAS_reduction/ID1hKLk9">PTAS reduction</a> 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 <a href="/facts/L-reduction/k71t0luq">L-reductions</a>, which imply PTAS reductions.
</p>
<h3>Examples</h3>
<p>One of the simplest APX-complete problems is <a href="/facts/MAX-3SAT/CXGU7IX3">MAX-3SAT-3</a>, a variation of the <a href="/facts/Boolean_satisfiability_problem/wBVRjWoy">Boolean satisfiability problem</a>. In this problem, we have a Boolean formula in <a href="/facts/Conjunctive_normal_form/B3sY1lTW">conjunctive normal form</a> 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.
</p><p>Other APX-complete problems include:
</p>
<ul><li><a href="/facts/Independent_set_(graph_theory)/ksu46kdz">Max independent set</a> 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).</li>
<li><a href="/facts/Vertex_cover/WK86bJvf">Min vertex cover</a>. The complement of any maximal independent set must be a vertex cover.</li>
<li><a href="/facts/Dominating_set/3xX4kSnP">Min dominating set</a> in bounded-degree graphs.</li>
<li>The <a href="/facts/Travelling_salesman_problem/2WEKVLnV">travelling salesman problem</a> when the distances in the graph satisfy the conditions of a <a href="/facts/Metric_(mathematics)/RkUptSo8">metric</a>. TSP is <a href="/facts/Combinatorial_optimization/PTcloS79">NPO-complete</a> in the general case.</li>
<li>The <a href="/facts/Token_reconfiguration/X92Fc3MD">token reconfiguration</a> problem, via <a href="/facts/L-reduction/k71t0luq">L-reduction</a> from set cover.</li></ul>
<h2 id="related-complexity-classes">Related complexity classes</h2>
<h3>PTAS</h3>
<p class="note">Main article: <a href="/facts/Polynomial-time_approximation_scheme/52Chjx9y">Polynomial-time approximation scheme</a></p>
<p>PTAS (<i>polynomial time approximation scheme</i>) 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.
</p>
<h3>APX-intermediate</h3>
<p>Unless <a href="/facts/P_%3D_NP_problem/xoC7Ruda">P = NP</a>, 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 <a href="/facts/Bin_packing_problem/T67Qe934">bin packing problem</a> 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.
</p><p>One other example of a potentially APX-intermediate problem is <a href="/facts/Edge_coloring/AcdpUxCv">min edge coloring</a>.
</p>
<h3>f(n)-APX</h3>
<p>One can also define a family of complexity classes 
  
    
      
        f
        (
        n
        )
      
    
    {\displaystyle f(n)}
  
-APX, where 
  
    
      
        f
        (
        n
        )
      
    
    {\displaystyle f(n)}
  
-APX contains problems with a polynomial time approximation algorithm with a 
  
    
      
        O
        (
        f
        (
        n
        )
        )
      
    
    {\displaystyle O(f(n))}
  
 approximation ratio. One can analogously define 
  
    
      
        f
        (
        n
        )
      
    
    {\displaystyle 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 <a href="/facts/Approximation-preserving_reduction/hTBEQJ4g">AP-reductions</a> 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.
</p><p>Log-APX-complete, consisting of the hardest problems that can be approximated efficiently to within a factor logarithmic in the input size, includes <a href="/facts/Dominating_set/3xX4kSnP">min dominating set</a> when degree is unbounded.
</p><p>Poly-APX-complete, consisting of the hardest problems that can be approximated efficiently to within a factor polynomial in the input size, includes <a href="/facts/Independent_set_(graph_theory)/ksu46kdz">max independent set</a> in the general case.
</p><p>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.
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Approximation-preserving_reduction/hTBEQJ4g">Approximation-preserving reduction</a></li>
<li><a href="/facts/Complexity_class/IIKrcTbP">Complexity class</a></li>
<li><a href="/facts/Approximation_algorithm/BWlf7M32">Approximation algorithm</a></li>
<li><a href="/facts/Max/min_CSP/Ones_classification_theorems/PBJz3TTx">Max/min CSP/Ones classification theorems</a> - a set of theorems that enable mechanical classification of problems about Boolean relations into approximability complexity classes</li>
<li><a href="/facts/MaxSNP/nKmjs3qz">MaxSNP</a> - a closely related subclass</li></ul>

<ul><li><i><a href="/facts/Complexity_Zoo/htGK5zuz">Complexity Zoo</a></i>: <a href="https://complexityzoo.net/Complexity_Zoo:A#apx">APX</a></li>
<li>C. Papadimitriou and M. Yannakakis. <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.89.3995&rep=rep1&type=pdf">Optimization, approximation and complexity classes</a>. Journal of Computer and System Sciences, 43:425–440, 1991.</li>
<li>Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, <a href="/facts/Marek_Karpinski/XPxNRbPA">Marek Karpinski</a> and <a href="/facts/Gerhard_J._Woeginger/beUa9kJr">Gerhard Woeginger</a>. <a href="https://www.csc.kth.se/~viggo/wwwcompendium/node225.html">Maximum Satisfiability</a> <a href="https://web.archive.org/web/20070413152307/https://www.csc.kth.se/~viggo/wwwcompendium/node225.html">Archived</a> 2007-04-13 at the <a href="/facts/Wayback_Machine/nmQ3a6JC">Wayback Machine</a>. <a href="https://www.csc.kth.se/%7Eviggo/wwwcompendium/"><i>A compendium of NP optimization problems</i></a> <a href="https://web.archive.org/web/20070405050438/https://www.csc.kth.se/~viggo/wwwcompendium/">Archived</a> 2007-04-05 at the <a href="/facts/Wayback_Machine/nmQ3a6JC">Wayback Machine</a>.</li></ul>

APX open-in-new

APX