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 [371] 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 [119]. More recently, another restriction of the PTAS-reducibility, called E-reducibility, has been introduced in [290].
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 [371]. Recently was shown that the closures of these classes under PTAS-reduction were identical to APX [290] and [121]. 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 [312]. The closures of these classes under PTAS-reduction have recently been shown to be identical to NPO PB [117]. In the compendium we therefore always use NPO PB-complete instead of MAX PB- complete and MIN PB-complete.