Approximation Algorithm
近似算法は多項式時間で NP-hard 問題の近似最適解を与え、解の品質が最適の某比率内にあることを保証する。
目的
NP-hard 問題に保証付き多項式時間近似解を提供する。
メカニズム
α-近似：解値 ≤ α*OPT（最小化）または ≥ OPT/α（最大化）。例：頂点被覆 2-近似、TSP 度量版 1.5-近似（Christofides）。PTAS は任意 ε に対し (1+ε)-近似を与える。
ユースケース
- NP 困難（NP-hard）問題の近似
- 組み合わせ最適化（Combinatorial Optimization）
- アルゴリズムの理論保証