Content deleted Content added
m Typo fixing + Check Wikipedia fixes:(0) using AWB |
m Travelling salesman problem : "TSP" link correction |
||
Line 48:
* ''NPO(I)'': Equals [[FPTAS]]. Contains the [[Knapsack problem]].
* ''NPO(II)'': Equals [[PTAS]]. Contains the [[Makespan scheduling problem]].
* ''NPO(III)'': :The class of NPO problems that have polynomial-time algorithms which computes solutions with a cost at most ''c'' times the optimal cost (for minimization problems) or a cost at least <math>1/c</math> of the optimal cost (for maximization problems). In Hromkovic's book, excluded from this class are all NPO(II)-problems save if P=NP. Without the exclusion, equals APX. Contains [[MAX-SAT]] and metric [[Travelling salesman problem|TSP]].
* ''NPO(IV)'': :The class of NPO problems with polynomial-time algorithms approximating the optimal solution by a ratio that is polynomial in a logarithm of the size of the input. In Hromkovic's book, excluded from this class are all NPO(III)-problems save if P=NP. Contains the [[set cover]] problem.
* ''NPO(V)'': :The class of NPO problems with polynomial-time algorithms approximating the optimal solution by a ratio bounded by some function on n. In Hromkovic's book, excluded from this class are all NPO(IV)-problems save if P=NP. Contains the [[Travelling salesman problem|TSP]] and [[Max Clique]] problems.
Another class of interest is NPOPB, NPO with polynomially bounded cost functions. Problems with this condition have many desirable properties.
| |||