Optimization problem: Difference between revisions

Revision as of 07:59, 12 May 2010

Revision as of 08:38, 12 May 2010

Line 49:

* ''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[[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, 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 [[Clique_problem|Max Clique problems]].