Exact algorithm: Difference between revisions
Content deleted Content added
| Line 21: | Line 21: | ||
== See also == |
== See also == |
||
* [[Approximation-preserving reduction |
* [[Approximation-preserving reduction]] |
||
* [[APX]] is the class of problems with some constant-factor approximation algorithm |
* [[APX]] is the class of problems with some constant-factor approximation algorithm |
||
* [[Heuristic algorithm]] |
* [[Heuristic algorithm]] |
||
Revision as of 02:43, 7 May 2016
In computer science and operations research, exact algorithms are algorithms that always solve an optimization problem to optimality. Unless P = NP, such an algorithm cannot run in worst-case polynomial time but 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.