Exact algorithm

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

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]


  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.