Completeness in approximation classes

In this section we define a natural approximation preserving reducibility and introduce the notion of completeness both in NPO and in APX.

Definition 8  

Let A and B be two NPO problems. A is said to be PTAS-reducible to B, in symbols $A \leq_{\mbox{\sc PTAS}} B$, if three functions f, g, and c exist such that:

1.

For any $x \in I_A$ and for any rational $\varepsilon \in (1,\infty)$, $f(x,\varepsilon ) \in I_B$ is computable in time polynomial with respect to |x|.

2.

For any $x \in I_A$, for any $y\in sol_B(f(x,\varepsilon ))$, and for any rational $\varepsilon \in (1,\infty)$, $g(x,y,\varepsilon ) \in sol_A(x)$ is computable in time polynomial with respect to both |x| and |y|.

3.

$c: (1,\infty) \rightarrow (1,\infty)$ is computable and invertible.

4.

For any $x \in I_A$, for any $y\in sol_B(f(x,\varepsilon ))$, and for any rational $\varepsilon \in (1,\infty)$,

$$R_B(f(x,\varepsilon ),y) \leq c(\varepsilon ) \mbox{ implies } R_A(x,g(x,y,\varepsilon )) \leq \varepsilon .$$

Remark 1  

In [393] a different kind of reducibility between optimization problems is defined which is called L-reducibility. It is possible to prove that, within APX, the L-reducibility is a restriction of the PTAS-reducibility [127]. More recently, another restriction of the PTAS-reducibility, called E-reducibility, has been introduced in [305].

Proposition 1   If $A \leq_{\mbox{\sc PTAS}} B$ and $B \in \mbox{\sc Apx}$ (respectively, $B \in \mbox{\sc PTAS}$), then $A \in \mbox{\sc Apx}$ (respectively, $A \in \mbox{\sc PTAS}$).

Definition 9  

A problem $A \in \mbox{\sc NPO}$ is NPO-complete if, for any $B \in \mbox{\sc NPO}$, $B \leq_{\mbox{\sc PTAS}} A$.

Definition 10  

A problem $A \in \mbox{\sc NPO}$ is APX-hard if, for any $B \in \mbox{\sc Apx}$, $B \leq_{\mbox{\sc PTAS}} A$. An APX-hard problem is APX-complete if it belongs to APX.

From Proposition 1 it immediately follows that if an NPO problem A is NPO-complete (respectively, APX-hard) then it does not belong to APX (respectively, PTAS). It is also possible to prove that if A is NPO-complete (respectively, NPO PB-complete) then it cannot be approximated within $2^{n^\varepsilon }$ (respectively, $n^\varepsilon$) for some $\varepsilon >0$.

The syntactically defined classes MAX SNP (containing e.g. MAXIMUM 3-SATISFIABILITY and MAXIMUM CUT) and MAX NP (containing e.g. MAXIMUM SATISFIABILITY) were defined in [393]. Recently was shown that the closures of these classes under PTAS-reduction were identical to APX [305] and [129]. In the compendium we therefore always use the term APX-complete instead of MAX SNP-complete and APX-hard instead of MAX SNP-hard.

The classes MAX PB and MIN PB consisting of the polynomially bounded maximization and minimization problems, respectively, were defined in [329]. The closures of these classes under PTAS-reduction have recently been shown to be identical to NPO PB [125]. In the compendium we therefore always use NPO PB-complete instead of MAX PB-complete and MIN PB-complete.