Skip to content

Approximation as Strategy

For intractable problems, algorithms with provable approximation bounds (within factor k of optimal) provide tractable solutions with quantified quality guarantees, trading exactness for computability.

Tension Addressed

Exact vs. Approximate Solutions (principled embrace of approximation)

Recognizable As

"2-approximation algorithm," PTAS/FPTAS terminology, bounded suboptimality guarantees, probabilistically approximately correct (PAC) learning, Monte Carlo methods

Canonical Sources

Vazirani, Approximation Algorithms (2001); Hochbaum, Approximation Algorithms for NP-Hard Problems (1996)

Transfers To

Machine learning (bias-variance trade-off), numerical computing, engineering tolerances, statistical sampling, real-time systems

Sub-concepts: - Approximation ratio: Quantified bound on distance from optimal - Randomized algorithms: Trading determinism for efficiency - Heuristics vs. approximations: Heuristics lack bounds; approximations have guarantees