다항 시간 근사 해법
From Wikipedia, the free encyclopedia
다항 시간 근사 해법(polynomial-time approximation scheme, PTAS)은 최적화 문제에 대한 근사 알고리즘의 한 종류이다. 주로 NP-난해 문제에 적용된다.
PTAS는 어떤 주어진 상수 에 대해서, 최적해로부터
배를 넘지 않는 해답을 찾아내는 알고리즘을 의미한다. 예를 들어, 유클리드 공간상의 외판원 문제에 대한 PTAS는 길이가
을 넘지 않는 순회 경로를 만들어낸다. 여기서 L은 가장 짧은 순회 경로의 길이이다. (참고로, 일반적인 외판원 문제에 대한 근사 알고리즘은 P=NP가 아닌 한 존재하지 않는다.)
EPTAS(efficient polynomial-time approximation scheme)는 PTAS 알고리즘 중에서 시간 복잡도가 꼴인, 즉 시간 복잡도를 대문자 O 표기법으로 표시했을 때
에 독립적인
의 꼴로 표현될 수 있는 알고리즘을 의미한다. 예를 들어,
는 EPTAS이다.
FPTAS(fully polynomial-time approximation scheme)는 EPTAS보다 더 강한 조건으로, PTAS 알고리즘 중에서 시간 복잡도가 에 대해서 다항 시간을 만족해야 한다. 예를 들어,
는 FPTAS를 만족하며,
는 PTAS이지만 FPTAS는 아니다.