Exact algorithm

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

References

  1. Fomin, Fedor V.; Kaski, Petteri (March 2013), "Exact Exponential Algorithms", Communications of the ACM 56 (3): 80–88, doi:10.1145/2428556.2428575.
  2. Fomin, Fedor V.; Kratsch, Dieter (2010). Exact Exponential Algorithms. Springer. p. 203. ISBN 978-3-642-16532-0.
This article is issued from Wikipedia - version of the Tuesday, March 08, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.