nearoptimal

Nearoptimal is a term used to describe solutions, strategies, or controls that are close to the best possible outcome for a given optimization problem. In algorithm design and operations research, near-optimal results are typically guaranteed by approximation bounds that quantify how far a produced solution may be from the optimum.

A standard formalism uses either multiplicative or additive measures of closeness. For a minimization problem with true optimum OPT, a solution with cost C is called α-approximate if C ≤ α·OPT for some α ≥ 1; as α approaches 1, the solution becomes near-optimal. Alternatively, an additive bound C ≤ OPT + ε specifies additive closeness. In reinforcement learning, an ε-optimal policy achieves value within ε of the optimal value.

Near-optimality is central when exact solutions are intractable, as in many NP-hard problems. Approximation algorithms and fully polynomial-time approximation schemes (FPTAS) provide near-optimal solutions with provable guarantees. Examples include the metric traveling salesman problem, where the Christofides algorithm yields a 1.5-approximation, and the knapsack problem, which admits an FPTAS.

Limitations include the dependence on knowledge of OPT or bounds, constants in the approximation ratio, and practical performance on specific instances. Near-optimal guarantees do not always reflect real-world outcomes, especially if the bound is loose or problem structure is specialized.

See also: approximation algorithm, approximation ratio, PTAS, FPTAS, epsilon-optimal, suboptimality gap.