Exact algorithm explained

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

• 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

Notes and References

1. .
2. Book: Fomin. Fedor V.. Kratsch. Dieter. Exact Exponential Algorithms. limited. Springer. 2010. 978-3-642-16532-0. 203.