Definition
Exact Algorithm
An exact algorithm is an algorithm for an optimisation problem that returns an optimal solution for every valid problem instance.
For a decision problem, an exact algorithm returns the correct yes/no answer for every valid instance.
Difference from Approximation
An exact algorithm gives correctness, not merely closeness.
For an optimisation problem with objective value returned by the algorithm and optimum value , exactness means
for every instance .
An approximation algorithm may return a non-optimal feasible solution, but it must prove a bound on how far the returned value can be from the optimum.