Class Description

MinPB: MinNP Polynomially Bounded

Same as MaxPB but for minimization instead of maximization problems.

Linked From

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

More about...