Approximation Algorithm¶

A polynomial-time optimization algorithm that always returns a feasible solution with a proved worst-case quality bound relative to the optimum.

Version: v4 · 2026-09-19 · History
Domain-specific #: 1299
Domain group: Applied Sciences & Engineering
Origin domain: Computer Science & Software Engineering
Subdomains: Theoretical Computer Science, Approximation Algorithms → Computer Science & Software Engineering

Core Idea¶

An approximation algorithm is a polynomial-time algorithm for an optimization problem that returns a feasible solution and carries a proved worst-case guarantee relating that solution's objective value to the optimum. It addresses problems for which exact optimization is computationally difficult by weakening optimality in a controlled, quantified way rather than abandoning proof.

For a minimization problem with nonnegative objective, an algorithm is commonly called an \(\alpha\)-approximation, \(\alpha\ge1\), when every instance \(I\) yields a feasible solution \(A(I)\) satisfying.

How would you explain it like I'm…

Fast Answer With a Promise

Some puzzles are so hard that finding the very best answer would take a computer forever. An approximation algorithm is a quick recipe that always finds an answer that works, and comes with a promise, checked with math, that it's never too far from the best one, like never more than twice as long as the shortest route.

Fast With a Proven Promise

Some computer problems, like planning the shortest trip through many cities, are so hard that finding the perfect answer could take far too long. An approximation algorithm is a fast method that always gives a usable answer and comes with a proof that its answer is never worse than the best one by more than a set amount. For example, it might promise its route is never more than twice as long as the shortest possible route, on every single puzzle, not just usually. A shortcut that often works well but has no proof doesn't count. And a method with a promise that is too slow doesn't count either.

Provably Near-Optimal Algorithms

An approximation algorithm is a fast (polynomial-time) algorithm for an optimization problem that always returns a valid solution, together with a proof that the solution's value is within a certain factor of the best possible. For a minimization problem, an alpha-approximation guarantees a cost at most alpha times the optimum on every input; for maximization problems there are a few conventions for stating the ratio, so the convention must be named. These algorithms are used for problems where finding the exact optimum is believed to be computationally too hard. A heuristic that usually works well but has no proven worst-case bound is not an approximation algorithm, and neither is a method with a guarantee that takes exponential time. Common techniques include greedy choices, local search, and rounding the solution of a linear-programming relaxation.

An approximation algorithm is a polynomial-time algorithm for an optimization problem that returns a feasible solution together with a proved worst-case bound relating its objective value to the optimum. It addresses computationally hard optimization by weakening optimality in a controlled, quantified way rather than abandoning proof. For a minimization problem with nonnegative objective, an alpha-approximation (alpha at least 1) guarantees val(A(I)) at most alpha times OPT(I) on every instance I. For maximization, conventions vary: either val(A(I)) at least OPT(I)/alpha with alpha at least 1, or val(A(I)) at least rho times OPT(I) with rho between 0 and 1, so a responsible statement names the convention, the problem class, and whether the guarantee is deterministic, in expectation, or with high probability. The abstraction is the conjunction of efficient construction, feasibility, and a universal performance theorem: a fast heuristic that usually performs well is not an approximation algorithm in this sense, and a bounded procedure running in exponential time fails the computational requirement. Techniques such as greedy selection, local search, linear-programming relaxation and rounding, primal-dual methods, semidefinite relaxation, and randomized rounding are unified by the obligation to prove near-optimality on every permitted instance.

Scope of Application¶

Approximation algorithms are central for NP-hard optimization problems in graphs, scheduling, facility location, routing, packing, covering, clustering, network design, and resource allocation. The method is appropriate when worst-case quality matters and exact optimality is too expensive. Guarantees also enable principled composition: a planner knows the maximum objective degradation even on inputs unlike the benchmark suite.

The scope is bounded by the chosen model. Some problems have strong constant-factor algorithms; others admit a polynomial-time approximation scheme; others are hard to approximate within specified ratios unless standard complexity assumptions fail. Weighted, directed, metric, geometric, online, stochastic, and multiobjective variants may have different guarantees.

Clarity¶

Ratio direction is the most common source of confusion. For minimization, values above optimum are worse, so \(\alpha\ge1\) gives an upper bound. For maximization, values below optimum are worse; authors either invert the ratio or use a fraction at most one. The phrase “a 2-approximation” therefore needs the optimization direction and convention, even though the intended meaning is standard in context.

Manages Complexity¶

The abstraction replaces an unattainable demand—find the exact optimum efficiently—with a budgeted loss. Its proof converts inaccessible \(\operatorname{OPT}\) into an analyzable certificate, such as an LP relaxation value, a matching size, or a dual solution. Designers can then compare algorithms by ratio, runtime, restrictions, and practical overhead rather than by anecdotal quality.

Abstract Reasoning¶

An approximation proof typically builds a bridge between the algorithmic output and a bound on optimum. For minimization, if \(L(I)\le\operatorname{OPT}(I)\) and the algorithm proves \(\operatorname{val}(A(I))\le\alpha L(I)\), the ratio follows. The challenge is selecting a certificate that is simultaneously computable, valid, and tightly coupled to the construction.

Knowledge Transfer¶

Proof techniques transfer across problem families when their structural assumptions transfer. LP rounding moves from set cover to facility-location variants only when the relaxation and rounding preserve the relevant constraints. Metric routing algorithms use triangle inequality; applying their bounds to nonmetric costs is invalid. Greedy charging arguments transfer when each selected object can be charged to a bounded number of optimum objects.

Relationships to Other Abstractions¶

Current abstraction Approximation Algorithm Domain-specific

Parents (1) — outgoing typed relations

Approximation Algorithm is a kind of Approximation Prime

prime:approximation is the broader abstraction this entry instantiates: the algorithm returns a controlled good-enough result rather than exact optimum.

Hierarchy path (1) — routes to 1 parentless root

Approximation Algorithm → is a kind of Approximation → is a decomposition of Representation → presupposes Abstraction

Neighborhood in Abstraction Space¶

Approximation Algorithm sits in a sparse region of the domain-specific corpus (85^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (2769 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-25