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 a nonnegative counting quantity , an FPRAS is a randomized algorithm with the displayed guarantee, running in time polynomial in encoded input length, and . The usual constant-success definition is equivalent by independent repetition and a median. This counting notion differs from a deterministic fully polynomial-time approximation scheme for optimization.
For every , such a scheme returns a feasible solution within relative error and runs in time polynomial in the encoded instance size and in . Dependence polynomial only for each fixed epsilon is the weaker polynomial-time approximation-scheme requirement.
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.
For a minimization problem with positive optimum, this convention measures the relative excess . An epsilon-approximation always returns a feasible solution with excess at most . A multiplicative-ratio convention instead reports . State the convention explicitly rather than treating these two numbers as interchangeable.
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.