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.<ref>{{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}}.</ref> <ref>{{cite book |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] }}</ref>

== 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== {{reflist}}

Category:Computational complexity theory Category:Optimization algorithms and methods