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].
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].
Same as MaxPB but for minimization instead of maximization problems.
The subclass of NPO problems for which the cost function is guaranteed always to be bounded by a polynomial in n (the input size).
See [ACG+99].
NPOPB equals the closure of MaxPB under PTAS reductions [CKS+99].