다항 시간 근사 해법

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

다항 시간 근사 해법(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는 아니다.

바깥 고리[편집]