Approximation Algorithm
Approximation algorithms produce near-optimal solutions to NP-hard problems in polynomial time, guaranteeing solution quality within a factor of the optimum.
Purpose
To provide guaranteed polynomial-time approximate solutions for NP-hard problems.
Mechanism
α-approximation: the solution value is ≤ α*OPT (minimization) or ≥ OPT/α (maximization). Examples include the 2-approximation for vertex cover and the 1.5-approximation for metric TSP (Christofides). A PTAS gives a (1+ε)-approximation for any ε.
Use cases
- NP-hard approximation
- Combinatorial optimization
- Theoretical guarantees