Approximation and Heuristics¶

When optimal solutions are computationally intractable (NP-hard), algorithms with provable approximation ratios or empirically effective heuristics provide practical alternatives with understood quality bounds.

Tension Addressed¶

Simplicity vs. Optimality; Generality vs. Efficiency

Recognizable As¶

Polynomial-time algorithms for NP-hard problems with guaranteed ratio to optimal; greedy heuristics; local search; simulated annealing; genetic algorithms.

Canonical Sources¶

Vazirani, Approximation Algorithms, 2001; Johnson, "Approximation Algorithms for Combinatorial Problems," 1974

Transfers To¶

Operations research, logistics, VLSI design, machine learning hyperparameter tuning, resource allocation

Sub-concepts: - Approximation ratio: Provable worst-case bound on solution quality relative to optimal - Local search: Iterative improvement from initial solution; susceptible to local optima - Metaheuristics: Problem-independent frameworks (simulated annealing, genetic algorithms) for escaping local optima

The decision between exact and approximate methods depends on problem size, time constraints, and quality requirements. Understanding when "good enough" suffices is essential engineering judgment.