Exact algorithm: Difference between revisions
Content deleted Content added
Undo uninformative and likely self-promotional |
Bluelink 1 book for verifiability (prndis)) #IABot (v2.0.1) (GreenC bot |
||
| Line 16: | Line 16: | ||
|last2=Kratsch|first2=Dieter |
|last2=Kratsch|first2=Dieter |
||
|title=Exact Exponential Algorithms |
|title=Exact Exponential Algorithms |
||
|publisher=Springer |
|url=https://archive.org/details/exactexponential00fvfo|url-access=limited|publisher=Springer |
||
|year=2010 |
|year=2010 |
||
|isbn=978-3-642-16532-0 |
|isbn=978-3-642-16532-0 |
||
|page=[https://archive.org/details/exactexponential00fvfo/page/n217 203] |
|||
|page=203 |
|||
}}</ref> |
}}</ref> |
||
Latest revision as of 00:10, 15 June 2020
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.[1] [2]
See also
[edit]- 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
[edit]- ^ 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.