Content deleted Content added
m Dating maintenance tags: {{Citation needed}} |
→NP optimization problem: active link to makespan |
||
Line 69:
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 [[Polynomial-time approximation scheme|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 [[Juraj Hromkovič|Hromkovič]]'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, all NPO(III)-problems are excluded from this class unless P=NP. Contains the [[set cover]] problem.
| |||