An approximation algorithm efficiently returns a feasible solution with a proved performance guarantee relative to the optimum. The guarantee must specify whether the problem is a maximization or minimization problem.
For maximization, an approximation ratio means the returned feasible value is at least times the optimal value on every permitted instance. Some conventions instead report its reciprocal; specify the convention.
Articles by others on the same topic
An approximation algorithm is a type of algorithm used to find near-optimal solutions to optimization problems, particularly when dealing with NP-hard problems where finding the exact solution may be computationally infeasible. These algorithms are designed to guarantee solutions that are close to the optimal solution, often within a specified factor known as the approximation ratio.