Exact algorithm: Difference between revisions
Content deleted Content added
Fixed an incorrect statement that was too broad. |
No edit summary |
||
| 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. |
||
Optimal solution can be the ral solution nor the visible solution |
|||
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 |
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 |
||
Revision as of 13:05, 8 July 2019
In computer science and operations research, exact algorithms are algorithms that always solve an optimization problem to optimality. Optimal solution can be the ral solution nor the visible solution
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.