Confused about the definition of "Exact Algorithm"

Question

What does it mean by saying "an algorithm is exact" in terms of Optimization and/or Computer Science? I need a precisely logical/epistemological definition.

Answer 1

Exact and approximate algorithms are methods for solving optimization problems.

Exact algorithms are algorithms that always find the optimal solution to a given optimization problem.

However, in combinatorial problems or total optimization problems, conventional methods are usually not effective enough, especially when the problem search area is large and complex. Among other methods we can use heuristics to solve that problems. Heuristics tend to give suboptimal solutions. A subset of heuristics are approximation algorithms.

When we use approximation algorithms we can prove a bound on the ratio between the optimal solution and the solution produced by the algorithm.

E.g. In some NP-hard problems there are some polynomial-time approximation algorithms while the best known exact algorithms need exponential time.

For example while there is a polynomial-time approximation algorithm for Vertex Cover, the best exact algorithm (using memoization) runs in O(1.1889ⁿ) pp 62-63.