In this section we define a natural approximation preserving reducibility and introduce the notion of completeness both in NPO and in APX.
Let A and B be two NPO problems. A is said to be PTAS-reducible to B, in symbols
,
if three functions
f, g, and c exist such that:
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].
A problem
is NPO-complete if, for any
,
.
A problem
is APX-hard if, for any
,
.
An APX-hard problem is APX-complete if it belongs to APX.
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.