Approximation Complexity Class

Definition

Approximation Complexity Class

The approximation complexity class $\mathrm{APX}$ consists of NP-optimisation problems that admit a deterministic polynomial-time algorithm with a constant approximation ratio:

$$\mathrm{APX}:=\{\Pi \in \mathrm{NPO}:\exists c\ge 1\exists A\text{ polynomial-time}:\forall I,R_A(I)\le c\}.$$

The constant $c$ and algorithm $A$ are fixed for the problem $\Pi$ and must work for every feasible instance $I$. Writing

$$a=f_{\Pi }(I,A(I))$$

for the value returned by $A$, and $o={\mathrm{OPT}}_{\Pi }(I)$, the guarantee is

$$\{\begin{array}{ll}o\le a\le co,& \mathrm{goal}=\min ,\\ o/c\le a\le o,& \mathrm{goal}=\max .\end{array}$$

Here $A(I)$ must be feasible, so the inequalities $o\le a$ for minimisation and $a\le o$ for maximisation follow from optimality. The other inequality is the approximation guarantee. An individual member is an APX optimisation problem.

Quantifier Order

The definition has the order

$$\underset{\text{one constant}}{\underbrace{\exists c\ge 1}}\underset{\text{one algorithm}}{\underbrace{\exists A}}\underset{\text{every feasible instance}}{\underbrace{\forall I}}.$$

The factor $c$ may depend on the problem $\Pi$, but it cannot depend on the particular instance $I$ or its size $|I|$. For example, a guarantee of

$$R_A(I)\le \log |I|$$

does not prove membership in $\mathrm{APX}$ because the bound grows with the input size.

The running time of $A$ must satisfy

$$T_A(I)\le \mathrm{poly}(|I|).$$

Here, $\mathrm{poly}(|I|)$ uses poly notation. Unlike an approximation scheme, APX does not introduce an accuracy parameter $\epsilon$. It asks only whether some fixed constant-factor guarantee can be achieved in polynomial time.

Direction of the Guarantee

For minimisation, the algorithm may return a value larger than the optimum, but by at most a factor $c$:

$${\mathrm{OPT}}_{\Pi }(I)\le f_{\Pi }(I,A(I))\le c{\mathrm{OPT}}_{\Pi }(I).$$

For maximisation, the algorithm may return a value smaller than the optimum, but not below a $1/c$ fraction of it:

$$\frac{{\mathrm{OPT}}_{\Pi }(I)}{c}\le f_{\Pi }(I,A(I))\le {\mathrm{OPT}}_{\Pi }(I).$$

The symmetric factor $c\ge 1$ therefore describes both goals. These inequalities also remain meaningful when the optimum is zero, whereas a quotient such as $a/o$ may be undefined.

Containment

Every problem admitting a PTAS belongs to APX: fix any constant accuracy, such as $\epsilon =\frac{1}{2}$, and the scheme becomes a polynomial-time constant-factor approximation. By definition, every APX problem is an NP-optimisation problem. Hence,

$$\mathrm{PTAS}\subseteq \mathrm{APX}\subseteq \mathrm{NPO}.$$

The first containment compares classes of problems: here $\mathrm{PTAS}$ denotes the set of NP-optimisation problems that admit a PTAS.

Membership and Hardness

Membership in APX is an algorithmic upper bound: it asserts that a constant-factor approximation exists. It does not assert that the problem is difficult. A problem solvable exactly in polynomial time also belongs to APX by choosing $c=1$.

APX-hardness is a separate lower-bound notion defined through approximation-preserving reductions. A problem may be:

• in APX without being known to be APX-hard;
• APX-hard without being known to belong to APX;
• APX-complete when both statements hold.

Example

Constant-factor membership

Suppose a polynomial-time algorithm for a minimisation problem always returns a feasible solution satisfying

$$f_{\Pi }(I,A(I))\le 3{\mathrm{OPT}}_{\Pi }(I).$$

Taking $c=3$ proves that $\Pi \in \mathrm{APX}$.

A growing factor is insufficient

Suppose instead that the only known guarantee is

$$f_{\Pi }(I,A(I))\le (1+\log |I|){\mathrm{OPT}}_{\Pi }(I).$$

This guarantee alone does not prove that $\Pi \in \mathrm{APX}$ because its factor is not bounded by a constant independent of $|I|$.