Content deleted Content added
m Added an example of reductions used for optimization problems. |
Added subclasses of NPO. |
||
Line 47:
| isbn = 91-7170-082-X
}}</ref>
NPO is divided into the following subclasses according to their approximability:<ref name=Hromkovic02/>
* ''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 maximization problems) or a cost at least <math>1/c</math> of the optimal cost (for minimization 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 [[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 [[TSP]] and [[Max Clique]] problems.
Another class of interest is NPOPB, NPO with polynomially bounded cost functions. Problems with this condition has many desirable properties.
==Notes==
| |||