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 A PX .

 

 

From Proposition  1 it immediately follows that if an NPO problem A is NPO-complete (respectively, A PX -hard) then it does not belong to A PX (respectively, PTAS). It is also possible to prove that if A is NPO-complete (respectively, NPO PB-complete) then it cannot be approximated within (respectively, ) for some .

The syntactically defined classes M AX SNP (containing e.g. M AXIMUM 3-S ATISFIABILITY and M AXIMUM C UT ) and M AX NP (containing e.g. M AXIMUM S ATISFIABILITY ) were defined in [ 284 ]. Recently was shown that the closures of these classes under PTAS-reduction were identical to A PX \ [ 217 ] and [ 88 ]. In the compendium we therefore always use the term A PX -complete instead of M AX SNP - complete and A PX -hard instead of M AX SNP - hard .

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