It is easy to read “minimise” as “get as close to the minimum as possible”. But these describe different things. An optimisation problem specifies the target: among feasible solutions to an instance, find one with the smallest objective value :
An exact algorithm returns with . An approximation algorithm tackles the same problem, but relaxes what its algorithm must achieve. For a minimisation problem, a factor- guarantee means
The first inequality follows because is feasible; the second is the algorithm’s promise. Calling a task an optimisation problem does not say whether we will solve it exactly or approximately.
The distinction to keep
The objective function tells us what to optimise. An algorithm’s guarantee tells us how well it solves that optimisation problem. These are separate: the same problem can have both an exact algorithm and an approximation algorithm.
In particular, a claim that a solution is optimal requires . A bound such as with does not establish optimality. For a maximisation problem the inequality reverses, but the distinction is the same.