Optimization problem: Difference between revisions

Revision as of 23:19, 3 October 2008

Revision as of 20:33, 4 October 2008

Line 51:

* ''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 maximizationminimization problems) or a cost at least <math>1/c</math> of the optimal cost (for minimizationmaximization 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.