다항식 시간 근사 방식(PTAS)이란?
0-1 배낭 문제(0-1 Knapsack Problem)나 부분집합 합 문제(Subset Sum Problem)와 같은 NP-완전(NP-Complete) 문제에 대해서도 다항식 시간 안에 동작하는 근사 해법을 찾을 수 있습니다. 이러한 문제들은 실무에서 매우 자주 등장하기 때문에, 이를 효과적으로 다룰 방법이 반드시 필요합니다.
다항식 시간 근사 방식(Polynomial Time Approximation Scheme, PTAS)은 최적화 문제를 위한 근사 알고리즘의 한 유형입니다. 0-1 배낭 문제에는 의사 다항식(Pseudo-Polynomial) 해법이 존재하지만, 입력 값이 커지면 이 해법은 현실적으로 사용하기 어렵습니다. 바로 이럴 때 PTAS 기반 해법이 필요해집니다.
그래프 색칠 문제(Graph Coloring), K-센터 문제(K-Center Problem)처럼 아직 알려진 다항식 시간 해법이 없는 NP-완전 문제들도 많습니다. PTAS는 이러한 문제들을 근사적으로 풀기 위해 활용됩니다. PTAS 알고리즘은 ε > 0인 매개변수를 입력으로 받으며, 최소화 문제에서는 최적해의 (1 + ε)배 이내로, 최대화 문제에서는 최적해의 (1 − ε)배 이상으로 결과를 보장합니다.
예제
예를 들어, 최소화 문제에서 ε = 0.5로 설정한다고 가정해 봅시다. 이 경우 PTAS가 산출하는 해는 최적해의 약 1.5배 이내가 됩니다. 즉, 오차 범위 50% 이내의 근사해를 얻을 수 있는 것입니다.
여기서 중요한 점은 실행 시간과 정확도 사이의 상충 관계(trade-off)입니다. PTAS의 실행 시간은 입력 크기 n에 대해서는 반드시 다항식이어야 하지만, ε에 대해서는 지수적으로 증가할 수 있습니다. 따라서 ε을 아주 작게 만들면 더 정확한 해를 얻을 수 있지만, 그만큼 계산 비용이 급격히 늘어나게 됩니다.
참고: FPTAS와의 차이
ε에 대해서도 실행 시간이 다항식인 변형인 FPTAS(Fully Polynomial Time Approximation Scheme)도 존재합니다. FPTAS는 n과 1/ε 모두에 대해 다항식 시간에 동작하기 때문에, ε을 자유롭게 조절할 수 있어 실용성이 더 높습니다. 0-1 배낭 문제가 대표적인 FPTAS 적용 사례입니다.