Exact algorithm: Difference between revisions
Content deleted Content added
ClueBot NG (talk | contribs) m Reverting possible vandalism by 102.141.234.6 to version by Misof. Report False Positive? Thanks, ClueBot NG. (3636753) (Bot) |
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. |
||
Optimum solutions can be the real solution or the visible solution (Oyebola,2019) |
|||
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:09, 8 July 2019
In computer science and operations research, exact algorithms are algorithms that always solve an optimization problem to optimality. Optimum solutions can be the real solution or the visible solution (Oyebola,2019)
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.