다항 시간 근사 해법

다항 시간 근사 해법(polynomial-time approximation scheme, PTAS)은 최적화 문제에 대한 근사 알고리즘의 한 종류이다. 주로 NP-난해 문제에 적용된다.

PTAS는 어떤 주어진 상수 $\epsilon >0$에 대해서, 최적해로부터 $\epsilon$배를 넘지 않는 해답을 찾아내는 알고리즘을 의미한다. 예를 들어, 유클리드 공간상의 외판원 문제에 대한 PTAS는 길이가 $(1+\epsilon )L$을 넘지 않는 순회 경로를 만들어낸다. 여기서 L은 가장 짧은 순회 경로의 길이이다. (참고로, 일반적인 외판원 문제에 대한 근사 알고리즘은 P=NP가 아닌 한 존재하지 않는다.)

EPTAS(efficient polynomial-time approximation scheme)는 PTAS 알고리즘 중에서 시간 복잡도가 $f(\epsilon )g(n)$ 꼴인, 즉 시간 복잡도를 대문자 O 표기법으로 표시했을 때 $\epsilon$에 독립적인 $O(n^{c})$의 꼴로 표현될 수 있는 알고리즘을 의미한다. 예를 들어, $O(e^{1/\epsilon }n^{2})$는 EPTAS이다.

FPTAS(fully polynomial-time approximation scheme)는 EPTAS보다 더 강한 조건으로, PTAS 알고리즘 중에서 시간 복잡도가 $1/\epsilon$에 대해서 다항 시간을 만족해야 한다. 예를 들어, $O((1/\epsilon )^{2}n^{2})$는 FPTAS를 만족하며, $\Theta (n^{1/\epsilon })$는 PTAS이지만 FPTAS는 아니다.

외부 링크

• 복잡도 동물원: PTAS, EPTAS, FPTAS
• Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, and Gerhard Woeginger, A compendium of NP optimization problems - PTAS가 있는 NP 최적화 문제 목록