Analysis of Algorithms | Polynomial Time Approximation Scheme

읽기 전

• 해당 게시물은 작성자가 학습한 내용을 정리 및 요약 목적으로 작성되었으므로 오역 및 오개념이 있을 수 있습니다. 바로잡기 위한 의견을 제시해주시면 매우 감사하겠습니다.

다항 시간 근사 해법(Polynomial Time Approximation Scheme, PTAS)

다항 시간 근사 해법(Polynomial-Time Approximation Scheme, PTAS)는 다항 시간 해법이 존재하지 않는 NP 문제들의 해결을 위해 사용된다. 명확하게 정확도를 다룰 수는 없지만 원하는 수준까지의 정확도를 제공할 수 있다면 합리적으로 채택할 수 있는 해법이라고 간주한다.

이러한 해법들은 새로운 파라미터인 $\epsilon>0$을 가지고. 복잡도가 최적해로부터 $\epsilon$배를 넘지 않는다. 근사 해법이므로 PTAS의 시간 복잡도는 $n$에 대하여 $\epsilon$으로 표현되는 다항 관계를 가져야 하지만 $\epsilon$에 대해서는 지수관계 등 해법에 따라 다양하다. 예를 들면 해법이 가질 수 있는 시간 복잡도는 $O(n^{\frac{1}{\epsilon}})$일 수도 있고 $O(n^{\frac{1}{\epsilon}!})$일 수도 있다.

FPTAS(Fully Polynomial Time Approximation Scheme)

특정 PTAS가 시간 복잡도 $O(n^{\frac{1}{\epsilon}})$을 갖는다고 할 때, $\epsilon$의 값이 작아지면 작아질 수록 시간 복잡도의 값은 급격하게 증가한다. 이 문제를 해결하기 위해 좀 더 엄격하게 해법을 정의하는 FPTAS(Fully Polynomial Time Approximation Scheme)를 도입한다. FPTAS의 조건은 PTAS 알고리즘 해법 중에서 시간 복잡도가 $\cfrac{1}{\epsilon}$에 대해 다항시간을 만족해야 하므로 $O(\frac{1}{\epsilon}^2n^2)$은 FPTAS가 될 수 있지만 다항 관계가 성립하지 않는 $O(n^{\frac{1}{\epsilon}})$은 PTAS이다.

예제: 0-1 knapsack 문제에 FPTAS 적용

0-1 냅색 문제는 NP-완전 문제이다. 그리고 보통 DP를 사용한 의사 다항시간 해법을 사용한다. 그러나 만약 input 값이 커질 수록 적용하기에 부적합하므로 유사 해법이 요구된다. 한 가지 유사 해법으로는 Greedy 접근 방식이 있다. 모든 물건의 kg 당 가치를 계산한 뒤 무게가 W를 넘지 않는 선에서 kg 당 가장 가치가 높은 물건을 넣는 방식이다. 그러나 PTAS가 아니므로 정확도를 컨트롤할 수 없다.

0-1 냅색 문제에 대한 FPTAS를 제시하기 전에 $W$를 냅색의 용량, val[0,...,n-1]을 각 아이템의 가치, wt[0,...,n-1]을 각 아이템의 무게라고 하자.

1. 우선 val[]에서 가장 가치가 높은 아이템을 찾는다. 해당 아이템의 가치를 maxVal이라 하자.
2. 모든 가치에 대해 조정 변수 $k$를 선언하고 그 값을 $k = (maxVal \cdot \epsilon)/n$이라 하자.
3. 모든 물건의 가치에 대해 조정 변수 $k$를 나눈 뒤 내림한 값을 담은 새로운 배열 val'[]를 선언한다.
4. 낮춰진 가치들을 담은 새로운 배열 val'[]에 대해 DP 기반의 기존 해법을 적용한다.

이 방법은 $n$과 $\epsilon$에 대해 다항시간이 걸리므로 FPTAS이며 근사된 정확도는 $1-\epsilon$이다. 값의 중요하지 않은 자릿수는 낮춰버림으로써 $n$에 대한 다항식과, $\cfrac{1}{\epsilon}$에 묶이도록 하였다.

해법의 적용 예제

val = [12, 16, 4, 8]
wt = [ 3, 4, 5, 2 ]
W = 10
ε = 0.5

maxVal = 16 <- val 배열의 가장 큰 값
조정 변수 k = ( 16 * 0.5 ) / 4 = 2.0

val' = [ 6, 8, 2, 4 ]
wt = [ 3, 4, 5, 2 ]
W = 10 
위 값에 대해 기존 DP 알고리즘을 적용하면 된다.

왜 위 해법이 '최적값'$\cdot (1-\epsilon)$인가

OPT를 최적값, S를 FPTAS에 의해 생성된 집합이라고 하자. 그리고 집합 S의 물건 가치를 모두 더한 값을 val(S)라고 하면 val(S) >= (1 - ε)*OPT임을 증명해야 한다.

O를 최적해 알고리즘에 의해 생성된 집합이라고 하자. 그러면 val(O)는 '최적값'인 OPT가 된다. 그리고 위 해법에 따라 val(O) - k*val'(O) <= n*k이 성립함을 알 수 있다. (∵ val'[i] = floor(val[i]/k)이기 때문)

그리고 기존 DP 해법으로 생성된 val'(S)는 반드시 val'(O)보다 크거나 같다. (∵ O가 '최적해'이므로 좀 더 낮은 차원이기 때문) 그러므로 다음이 성립한다.

val'(S) >= k * val'(O)
        >= val(O) - n * k
        >= OPT - ε * maxVal [k  = (maxVal * ε) / n]
        >= OPT - ε * OPT [OPT >= maxVal]
        >= (1 - ε) * OPT

참고자료

1. Polynomial Time Approximation Scheme
2. wikipedia_다항 시간 근사 해법