Exact algorithm: Difference between revisions
Content deleted Content added
Marcocapelle (talk | contribs) removed Category:Mathematical optimization; added Category:Optimization algorithms and methods using HotCat |
Fixed an incorrect statement that was too broad. |
||
| Line 1: | Line 1: | ||
In [[computer science]] and [[operations research]], '''exact algorithms''' are [[algorithm]]s that always solve an optimization problem to optimality. |
In [[computer science]] and [[operations research]], '''exact algorithms''' are [[algorithm]]s that always solve an optimization problem to optimality. |
||
Unless [[P = NP]], an exact algorithm for an [[NP-hardness | NP-hard]] optimization problem cannot run in worst-case [[polynomial time]]. There has been extensive research on finding exact algorithms whose running time is exponential with a low base.<ref>{{citation |
|||
| last1 = Fomin | first1 = Fedor V. |
| last1 = Fomin | first1 = Fedor V. |
||
| last2 = Kaski | first2 = Petteri |
| last2 = Kaski | first2 = Petteri |
||
Revision as of 22:14, 13 May 2019
In computer science and operations research, exact algorithms are algorithms that always solve an optimization problem to optimality.
Unless P = NP, an exact algorithm for an NP-hard optimization problem cannot run in worst-case polynomial time. There has been extensive research on finding exact algorithms whose running time is exponential with a low base.[1] [2]
See also
- Approximation-preserving reduction
- APX is the class of problems with some constant-factor approximation algorithm
- Heuristic algorithm
- PTAS - a type of approximation algorithm that takes the approximation ratio as a parameter
References
- ^ Fomin, Fedor V.; Kaski, Petteri (March 2013), "Exact Exponential Algorithms", Communications of the ACM, 56 (3): 80–88, doi:10.1145/2428556.2428575.
- ^ Fomin, Fedor V.; Kratsch, Dieter (2010). Exact Exponential Algorithms. Springer. p. 203. ISBN 978-3-642-16532-0.