Exact algorithm
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.{{citation
| last1 = Fomin | first1 = Fedor V.
| last2 = Kaski | first2 = Petteri
| date = March 2013
| doi = 10.1145/2428556.2428575
| issue = 3
| journal = Communications of the ACM
| pages = 80–88
| title = Exact Exponential Algorithms
| url = http://cacm.acm.org/magazines/2013/3/161189-exact-exponential-algorithms/fulltext
| volume = 56}}.
|last1=Fomin|first1=Fedor V.
|last2=Kratsch|first2=Dieter
|title=Exact Exponential Algorithms
|url=https://archive.org/details/exactexponential00fvfo|url-access=limited|publisher=Springer
|year=2010
|isbn=978-3-642-16532-0
|page=[https://archive.org/details/exactexponential00fvfo/page/n217 203]
}}
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