다항 시간 근사 해법 문서 원본 보기

{{위키데이터 속성 추적}}
'''다항 시간 근사 해법'''(polynomial-time approximation scheme, '''PTAS''')은 [[최적화 문제]]에 대한 [[근사 알고리즘]]의 한 종류이다. 주로 [[NP-난해]] 문제에 적용된다.

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

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

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

== 외부 링크 ==

*복잡도 동물원: [https://web.archive.org/web/20061128071923/http://qwiki.caltech.edu/wiki/Complexity_Zoo#ptas PTAS], [https://web.archive.org/web/20061128071923/http://qwiki.caltech.edu/wiki/Complexity_Zoo#eptas EPTAS], [https://web.archive.org/web/20061128071923/http://qwiki.caltech.edu/wiki/Complexity_Zoo#fptas FPTAS]
*Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, [[Marek Karpinski]], and Gerhard Woeginger, [http://www.nada.kth.se/~viggo/wwwcompendium/ ''A compendium of NP optimization problems''] - PTAS가 있는 NP 최적화 문제 목록

{{전거 통제}}

[[분류:근사 알고리즘]]