근사 알고리즘

근사 알고리즘(approximation algorithm)은 어떤 최적화 문제에 대한 근사해를 구하는 알고리즘을 의미한다. 이 알고리즘은 가장 최적화되는 답을 구할 수는 없지만, 비교적 빠른 시간에 계산이 가능하며 어느 정도 보장된 근사해를 계산할 수 있다. 근사 알고리즘은 NP-완전 문제 등 현재 알려진 빠른 최적화 알고리즘이 없을 문제에 대해 주로 사용된다.

근사 비율

어떤 최적화 문제에 대해, 항상 $\rho$배를 벗어나지 않는 근사해를 구하는 알고리즘이 존재할 경우, 그 알고리즘을 $\rho$-근사 알고리즘이라고 부른다. 즉, 최적해가 OPT일 경우, 근사 알고리즘 $f(x)$는 항상

• $\mathrm{OPT}(x) \leq f(x) \leq \rho \mathrm{OPT}(x)$ ($\rho > 1$인 경우)
• $\rho \mathrm{OPT}(x) \leq f(x) \leq \mathrm{OPT}(x)$ ($\rho < 1$인 경우)

를 만족해야 한다.

더 보기

• 다항 시간 근사 해법

참고문헌

• 비제이 V. 바지라니 (2003). 《Approximation Algorithms》 (영어). 베를린: Springer. ISBN 3540653678