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

v3 · 2026-09-06 · History

Domain-specific #

1299

Origin domain

theoretical computer science

Subdomain

approximation algorithms

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.

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) — more general patterns this builds on

• Approximation Algorithm is a kind of Approximation Prime

  prime:approximation is the immediate parent: the algorithm returns a controlled good-enough result rather than exact optimum.

Hierarchy path (1) — routes to 1 parentless root

• Approximation Algorithm → Approximation → Representation → Abstraction

Neighborhood in Abstraction Space

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

Family — Complexity Reductions & Decidability (10 abstractions)

Nearest neighbors

• L-Reduction — 0.82
• PTAS Reduction — 0.82
• Semi-infinite programming — 0.81
• Bilinear program — 0.81
• 3-dimensional matching — 0.80

Computed from structural-signature embeddings · 2026-09-08