Has the same relation to NP as MaxSNP does to SNP.
Contains MaxPB.
The closure of MaxNP under PTAS reduction is APX [KMS+99], [CT94].
The subclass of NPO problems that admit constant-factor approximation algorithms. (I.e., there is a polynomial-time algorithm that is guaranteed to find a solution within a constant factor of the optimum cost.)
Contains PTAS.
Equals the closure of MaxSNP and of MaxNP under PTAS reduction [KMS+99], [CT94].
Defined in [ACG+99].
The subclass of MaxNP problems for which the cost function is guaranteed always to be bounded by a polynomial.
MinPB can be defined similarly.
Defined in [KT94].
The closure of MaxPB under PTAS reductions equals NPOPB [CKS+99].