Definition
Exact Algorithm
An exact algorithm is an algorithm for an optimisation problem that returns an optimal solution for every valid problem 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.