Class Description

MaxPB: MaxNP Polynomially Bounded

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].

Linked From

MaxNP: Maximization NP

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].

More about...


MinPB: MinNP Polynomially Bounded

Same as MaxPB but for minimization instead of maximization problems.

More about...


NPOPB: NPO Polynomially Bounded

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].

More about...