|
==Combinatorial optimization problem==
{{Main|Combinatorial optimization}}
Formally, a [[combinatorial optimization]] problem <math>A</math> is a quadruple{{Citation needed|date=January 2018}} <math>(I, f, m, g)</math>, where
* <math>I</math> is a [[Set (mathematics)|set]] of instances;
| isbn = 978-3-540-65431-5
|display-authors=etal}}</ref>
=== NP optimization problem ===
An ''NP-optimization problem'' (NPO) is a combinatorial optimization problem with the following additional conditions.<ref name=Hromkovic02>{{citation
| last1 = Hromkovic | first1 = Juraj
| year = 2002
| edition = 2nd
| title = Algorithmics for Hard Problems
| series = Texts in Theoretical Computer Science
| publisher = Springer
| isbn = 978-3-540-44134-2
}}</ref> Note that the below referred [[Polynomial|polynomials]] are functions of the size of the respective functions' inputs, not the size of some implicit set of input instances.
* the size of every feasible solution <math>y\in f(x)</math> is polynomially [[Bounded set|bounded]] in the size of the given instance <math>x</math>,
* the languages <math>\{\,x\,\mid\, x \in I \,\}</math> and <math>\{\,(x,y)\, \mid\, y \in f(x) \,\}</math> can be [[decidable language|recognized]] in [[polynomial time]], and
* <math>m</math> is [[polynomial time|polynomial-time computable]].
This implies that the corresponding decision problem is in [[NP (complexity)|NP]]. In computer science, interesting optimization problems usually have the above properties and are therefore NPO problems. A problem is additionally called a P-optimization (PO) problem, if there exists an algorithm which finds optimal solutions in polynomial time. Often, when dealing with the class NPO, one is interested in optimization problems for which the decision versions are [[NP-completeness|NP-complete]]. Note that hardness relations are always with respect to some reduction. Due to the connection between approximation algorithms and computational optimization problems, reductions which preserve approximation in some respect are for this subject preferred than the usual [[Turing reduction|Turing]] and [[Karp reduction]]s. An example of such a reduction would be the [[L-reduction]]. For this reason, optimization problems with NP-complete decision versions are not necessarily called NPO-complete.<ref name=Kann92>{{citation
| last1 = Kann | first1 = Viggo
| year = 1992
| title = On the Approximability of NP-complete Optimization Problems
| publisher = Royal Institute of Technology, Sweden
| 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 [[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.
* ''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, all NPO(IV)-problems are excluded from this class unless P=NP. Contains the [[Travelling salesman problem|TSP]] and [[Clique_problem|Max Clique problems]].
Another class of interest is NPOPB, NPO with polynomially bounded cost functions. Problems with this condition have many desirable properties.
==References==
| 