완전 다항식 시간 근사 체계

완전 다항식 시간 근사 체계(FPTAS)는 최적화 문제에 대한 대략적인 최적의 솔루션을 찾기 위한 알고리즘이다.FPTAS는 문제의 인스턴스와 파라미터 >0 을 입력으로 받아들입니다.값이 -인 솔루션을 출력으로 반환합니다.

• 최적 솔루션의 최소 1배 - 0.5배 - 최대화에 문제가 있는 경우 또는 -
• 최소화에 문제가 있는 경우 최적 솔루션의 최대 1 + µ배입니다.

중요한 것은 FPTAS의 런타임은 문제 크기 및 1/1µ 단위로 다항식이라는 것입니다.이는 일반 다항식 시간 근사 체계(PTAS)와는 대조적이다.일반 PTAS의 실행 시간은 각 특정 θ에 대한 문제 크기에서는 다항식이지만 1/^[1]θ에서는 기하급수적일 수 있습니다.

FPTAS라는 용어는 FPTAS를 갖는 최적화 문제의 클래스를 지칭하는 데 사용될 수도 있다. FPTAS는 PTAS의 서브셋이며, P = NP가 아닌 한 엄격한 ^[2]서브셋이다.

다른 복잡도 클래스와의 관계

FPTAS의 모든 문제는 표준 파라미터화와 ^[3]관련하여 고정 파라미터로 추적할 수 있다.

다항식 유계 목적 함수의 강한 NP-하드 최적화 문제는 P=^[4]NP가 아니면 FPTAS를 가질 수 없다.그러나, 역행은 실패한다. 예를 들어 P가 NP와 같지 않은 경우, 두 개의 제약 조건을 가진 배낭은 강한 NP-hard가 아니며, 최적 목표가 다항식으로 ^[5]경계가 되어도 FPTAS가 없다.

다이내믹 프로그램을 FPTAS로 변환

Woorginger는^[6] 특정 클래스의 동적 프로그램을 FPTAS로 변환하기 위한 일반적인 체계를 제시했습니다.

입력

이 방식에서는 다음과 같이 입력이 정의되는 최적화 문제를 처리합니다.

• 입력은 n개의 벡터, x₁,...x로_n 구성됩니다.
• 각 입력 벡터는 음이 아닌 정수$$$(\displaystyle$ a$)$로 구성됩니다. $여기$서 \$displaystyle$ a는$$ 입력에 의존할 수 있습니다.
• 입력 벡터의 모든 구성요소는 바이너리로 인코딩됩니다.따라서 문제의 크기는 O(n+log(X)입니다.X는 모든 벡터의 모든 성분의 합입니다.

매우 심플한 다이내믹 프로그램

이 문제는 상태를 사용하는 Dynamic Programming(DP; 다이내믹프로그래밍) 알고리즘이 있다고 가정합니다.각 상태는 음이 아닌 정수$$ b$(b\displaystyle$ b$)$로 구성된 벡터이며, $여기$서 b$(b\displaystyle$b)는$$ 입력과 독립적입니다.DP는 n개의 스텝으로 동작합니다.각 스텝 i에서 입력_i x를 처리하여 일련의 상태_i S를 구축한다.각 상태는 입력 x₁,…,x를_i 사용하여 문제에 대한 부분 해결책을 인코딩합니다. DP의 구성요소는 다음과 같습니다.

• 초기 상태의 집합₀ S.
• 전환 함수의 집합 F.F 의 각 함수 f 는, 페어(state, input)를 새로운 스테이트에 매핑 합니다.
• 상태를 값에 매핑하는 목적 함수 g.

DP의 알고리즘은 다음과 같습니다.

• S : = 초기 상태 집합으로 합니다₀.
• k = 1 ~ n 의 경우:
  • S_k : = {f(s,x_k) f in F, s in_k−1 S}로 하자.
• 최소/최대 {g(s)의 S}을_n(를) 출력합니다.

DP의 실행 시간은 가능한 상태의 수에 따라 선형입니다.일반적으로 이 숫자는 입력 문제의 크기가 지수일 수 있습니다. 즉, O(n^b V)일 수 있습니다. 여기서 V는 상태에 나타날 수 있는 정수보다 큰 정수입니다.V가 O(X)에 있는 경우, 실행 시간은 O(n^b X)에 있고, O(log X)에 있는 문제 크기가 지수적이므로 의사 다항 시간일 뿐입니다.

이를 다항식으로 만드는 방법은 상태 공간을 트리밍하는 것입니다. 각 단계에서 가능한 모든 상태를 유지하는 대신 상태의 하위 집합만 유지하고 다른 상태와 "충분히 가까운" 상태를 제거합니다.특정 상황에서는 목표 값을 너무 많이 변경하지 않는 방식으로 이 트리밍을 수행할 수 있습니다.

이를 공식화하기 위해, 우리는 당면한 문제가 문제의 정도 벡터라고 불리는 음이 아닌 정수 벡터 d = (d₁,...d_b)를 가지고 있다고 가정한다.모든 실수 r> 1따라서 1일 각 좌표 j,...,b:r− djs1, ⋅ j가 두 state-vectors s1,s2(d,r)-close 있다고 말한다 ≤ s2j≤ rdj⋅ s1, j{\displaystyle r^{-d_{j}}\cdot s_{1,j}\leq s_{2,j}\leq r^{d_{j}}\cdot s_{1,j}}(특히, 만약 dj=0을 위한 j, 그때는 밖 1, j)s2, j. $(\displaystyle s_{1,j}=s_{2,j})$

다음 세 가지 조건을 만족하는 문제를 초베네볼트라고 합니다.

1. 근접성은 전환 기능을 통해 유지됩니다.임의의 r>1, 임의의 F의 전이함수 f, 임의의 입력벡터 x 및 임의의 2개의 상태벡터에₁ 대해서₂, s가 s에 가까운 경우, f(s₂,x₁)는 f(s₂,x)에 가까운 경우, f(s₁,x)가 f(s,x)에 가까운 경우.
   • 이를 위한 충분한 조건은 다음과 같이 확인할 수 있다.F의 모든 함수 f(s,x) 및 1, …, b의 모든 좌표 j에 대해 f(s,x)의 j번째 좌표를 나타낸다_j.이_j f는 b+a 변수에서 정수 함수로 볼 수 있습니다.이러한_j 모든 f가 음수가 아닌 계수를 갖는 다항식이라고 가정합니다.s=(z^d1,...z^db)와 x=(1,...1)를 대입하여 단일 변수 z의 다항식으로 변환합니다.z 단위의 결과 다항식의 정도가 최대_j d이면 조건 1을 만족한다.
2. 근접성은 값 함수에 의해 유지됩니다.정수 G 0 0(값 함수 g와 정도 벡터 d의 함수)이 존재하며, 임의의 r>1 및 임의의 2개의 상태 벡터에₁₂ 대해 다음과 같이 유지된다.s가₁ s에₂ (d,r)-근접하면 g(s₁) r^G r · g(s₂)(최소화 문제에서); g(s₁) r^(-G) r(s₂ · s · r )이다.
   • 이를 위한 충분한 조건은 함수 g가 음이 아닌 계수를 갖는 (b 변수의) 다항식 함수라는 것입니다.
3. 기술 조건:
   • F의 모든 전이함수 f와 값함수 g를 폴리타임으로 평가할 수 있다.
   • 변환 함수의 수 F는 n과 log(X)에서 다항식입니다.
   • 초기 상태의 집합₀ S는 n과 log(X)의 시간 다항식으로 계산할 수 있습니다.
   • V를 상태에서 좌표 j에 나타날 수 있는 모든 값의 집합이라고 가정하자_j.그러면, V의 모든_j 값의 ln은 기껏해야 다항식₁ P(n,log(X)이다.
   • d=0이면_j V의_j 카디널리티는 기껏해야 다항식₂ P(n,log(X)이다.

모든 극히 중대한 문제에 대해 동적 프로그램을 FPTAS로 변환할 수 있습니다.정의:

• $ϵ$\$displaystyle$ \ silon$$}$$ : = 필요한 근사비.
• ${\displaystyle r}$: ${\displaystyle =1}$ + ${\displaystyle \frac{2\mathrm{}}{}}$ 2 ${\displaystyle \frac{\mathrm{Gn}}{}}${ $displaystyle$ r : =$1$+ { \ $frac${ \ $silon$} { 2 Gn $}$ $。$여기서 G는 조건 2의 상수입니다.${\displaystyle \frac{1}{}}$ ln${\displaystyle \frac{r}{}}$ r${\displaystyle 1\frac{\mathrm{}}{}}$ ${\displaystyle \frac{1}{}}$ + 2 ${\displaystyle \frac{}{}}$ ${\$ { $displaystyle \ frac$ { 1$}${ \ $ln$ { r } \ $leq$1 + { \ $frac$ { 2 Gn } { \ $epsilon }$ $\}$ 。
• $L$: ${\displaystyle =}$ ${\displaystyle \lceil }$ ${\displaystyle \frac{{P\mathrm{}}_{}}{}}$1 ( ${\displaystyle \frac{n}{}}$, ${\displaystyle \frac{\log (}{}}$ (${\displaystyle \frac{}{X}}$) ln${\displaystyle \frac{}{}}$（ ${\displaystyle \frac{r}{}}$） ${\$ 、 { $display style$ L : = \$left$ \ $lceil${$P _$ { n , \ $log ( X$) } 、 { \ ln₁ ( r )$}$、 P$$\ of 、 、 \ 、 、 ( ( ( ( 、 、 、 、 ( ( ( ( ( ( ( ( 3 ( ( ( ( ( ( ( ( ( ( ( ( (3 ( 、 ( that that that that that that that that that that that that that that that$L{\displaystyle }$ ${\displaystyle \le }$ ${\displaystyle （}$ ${\displaystyle 1\mathrm{}}$+ ${\displaystyle 2\frac{\mathrm{}}{}}$ ${\displaystyle \frac{G}{}}$ ${\displaystyle \frac{}{}}$） ${\displaystyle {P\mathrm{}}_{}}$ 1${\displaystyle {}_{}}$（${\displaystyle n}$ 、 log${\displaystyle )}$ ${\displaystyle X}$ ）${\displaystyle }$displaydisplay $、$ { $displaystyle L$ \ $leq \$ left \ $lceil \$left ( $1$+ { \ $frac${ 2 $Gn$} { \ $epsilon$} } \ $right$） 。P1의 정의, state-vector i.에 나타날 수 있는 모든 정수도 그렇게 P_ᆫ(n,\log{X})\right\rceil}, 그래서 그것은 입력의 크기와 1/ϵ{1/\epsilon\displaystyle}에서 다항다. 또한, r L)eln ⁡ r⋅ L≥ eP1(n, 로그 ⁡)){\displaystyle r^{나는}=e^{\ln{r}}\cdot L\geq e^ᆯ(n,\log{x})}},s[0,r^L] 범위 내에 있습니다.
• 범위 [0,r^L]를 L+1 r 간격으로 분할합니다.$=$$I_{1}=[1,r];$$I_{2}=[r,r^{2};\ldots;$$I_{L}=[r^{L-1},r^{L$
• 상태 공간을 r-제곱으로 분할합니다. 도 d_k ≤ 1인 각 좌표 k는 위의 L+1 간격으로 분할됩니다. d = 0인_k 각 좌표는 P(n,log(X) 단일톤 구간으로 분할됩니다₂. 여기서₂ P는 위의 조건 3의 각 가능한 좌표 값에 대한 간격입니다.
  • 가능한 모든 상태는 정확히 하나의 r 박스에 포함되어 있습니다.두 개의 상태가 같은 r 박스에 있는 경우는, (d, r)-close 입니다.
• $R$: ${\displaystyle =}$ ( ${\displaystyle L}$+${\displaystyle 1}$ + ${\displaystyle {P\mathrm{}}_{}}$2 (${\displaystyle n}$ , ${\displaystyle \log x}$X${\displaystyle {}^{}}$)$$ { $displaystyle$ R : = ($L$ +$1$ + $P$_ {$2}$ ( $n$, \$log${$$X ) } }$。$
  • r박스 수는 최대 R입니다.b는 고정 상수이므로 이 R은 입력 크기 및${\displaystyle }$1/$${\({$displaystyle$ 1$/\epsilon$에서 다항식입니다.

FPTAS는 DP와 유사하게 동작하지만 각 단계에서 각 r박스에 정확히1개의 상태를 포함하는 작은 세트T로_k 설정 상태를 트리밍합니다.FPTAS 알고리즘은 다음과 같습니다.

• T : = S₀ = 초기 상태의 집합이라고 하자₀.
• k = 1 ~ n 의 경우:
  • U_k : = {f(s_k,x) f in F, s in_k−1 T}로 하자.
  • T_k : =를 U의 상태가_kk 하나 이상 포함된 각 r-box에 대해 T에서_k 정확히 하나의 상태를 유지하도록 한다.
• 최소/최대 {g(s)을 T 단위로_n 출력합니다.

FPTAS의 실행 시간은 각 T의_i 가능한 상태의 총 수에서 다항식입니다.이것은 최대 R의 총수이며, n, log(X) $및{\displaystyle \mathrm{}}$1$/"$ ({$display style$ 1$/\epsilon$의 다항식입니다.

U의_k 각 상태에_u 대해 서브셋T에는_k (d,r)에 가까운 상태가_u 적어도1개 포함되어 있는_t 것에 주의해 주세요.또_k, 각 U는 원래의 (미정리) DP내의 S의_k 서브셋이다.FPTAS의 정확성을 증명하기 위한 주요 조항은 다음과 같습니다.^{[6]: Lem.3.3}

0, …, n의 각 스텝 k에 대해서, S의 모든_k 상태_s s에 대해서, (d^k,r)에 가까운_s 상태_t s가 T에_k 존재한다.

그 증거는 k에 대한 유도에 의한 것이다.k=0의 경우 T=S가_k 있으며_k, 모든 상태는 (d,1)-근접합니다.보조항목이 k-1을 유지한다고 가정합니다.S의_k 모든 상태에_s 대해, f(s_s−,x)=s가_s 되도록 S의 이전_s- 상태_k-1 중 하나가 되자.유도 가정에 따르면 T에는_k-1 (d,r^k-1)-s에 가까운_s− 상태_t- s가 있다.근접성은 전이에 의해 유지되므로(위의 조건 1) f(s_t−,x)는 f(s_s−,x^k-1)=s에_s 가깝다.이 f(s_t−,x)는 U에 있습니다_k. 트리밍 후 T의_t 상태_k s는_t- f(s,x)에 가깝습니다.이_t s는 (d^k,r)에_s 가깝습니다.

이제 최적의 솔루션(즉, g(s*)=OPT)에 해당하는 S의_n 상태를^* 고려합니다.상기 약어로 T에는_n (d,rⁿ)-s에 가까운^* 상태 t*가 있다.근접성은 값 함수에 의해 유지되므로 최대화 문제에 대해서는 g(t*) r r^(-Gn) · g(s*)이다.$r{\displaystyle {}^{}}$- ${\displaystyle G^{}}$ n ${\displaystyle （}$ ${\displaystyle 1}$- ${\displaystyle ）}${ $displaystyle$ r^ { - $Gn$} \ $geq$ ( 1 - \ $epsilon$)$$}의 정의에 따라 g${\displaystyle }$( ${\displaystyle {}^{}}$ ${\displaystyle {}^{}}$ )${\displaystyle a}$ ${\displaystyle 、}$ O P${\displaystyle T}$ (${\displaystyle }$\ $display style$g ( $t$^ { * * ) \ ） 、 $、 geq$( 1 - \$epsilon$ )인수는 ${\displaystyle \mathrm{Opt}}$ $At$와 같이 동작합니다$.$

예

위 ^[6]정리에 의한 FPTAS를 갖는 극히 본질적인 문제의 예를 다음에 제시하겠습니다.

(가) 최대 합계를 최소화하는 것을 목적으로 하는 멀티웨이 번호 분할(등가적으로 동일 기계 스케줄링)은 극히 유익하다.여기서는 a = 1(입력값은 정수)과 b = 빈 수(고정된 것으로 간주)가 있습니다.각 상태는 b 빈의 합계를 나타내는 b 정수의 벡터입니다.b 함수가 있습니다.각 함수 j는 다음 입력을 bin j에 삽입하는 것을 나타냅니다.함수 g는 s의 가장 큰 원소를 선택합니다.S₀ = {(0,......0)}.극한-진도 조건은 도수차 d=(1,...1) 및 G=1로 만족한다.결과는 기계 수가 고정될 때마다 균일한 기계 스케줄링과 관련 없는 기계 스케줄링으로 확장됩니다(이것은 R - r 상자의 수가 b에서 지수적이기 때문에 필요합니다).${\displaystyle Pm}$ ${\displaystyle {}_{}}$ ${\displaystyle C_{}}$j$(\displaystyle$ \$max C_{$j$$}), ${\displaystyle Qm}$ ${\displaystyle {max}_{}}$C $j(\displaystyle$ \$max C_{$j$$}) ${\displaystyle {}_{}}$ ${\displaystyle {Rm}_{}}$ max C$$j(\$displaystyle \max$ C_${j$로 표시됩니다.

• 참고: 특수한 경우 b=2를 고려하십시오. 여기서 목표는 두 부품 합계의 차이의 제곱을 최소화하는 것입니다.동일한 DP를 사용할 수 있지만 이번에는 값 함수 g(s) = (s-s₁₂)²가 사용됩니다.이제, 조건 2가 위반된다: 상태₁ (s₁,s)와₁ (s₂,s)는 (d,r)-close일 수 있지만, g(s₁₁₁,s) = 0인 반면 g(s₂,s) > 0이므로 위의 정리를 적용할 수 없다.실제로 최적값이 0인지 여부를 결정하기 위해 폴리타임에 FPTAS를 사용할 수 있기 때문에 P=NP가 아닌 한 문제는 FPTAS를 가지지 않는다.

2. 동일하거나 균일한 기계(Qm ${\displaystyle {}_{}^{}}$ C ${\displaystyle j_{}^{}}$({$displaystyle \sum$ C_${j}^{$3}))$$의 큐브 작업 완료 시간의 합계는 a=1, b=3, d=(1,1,3)와 동등합니다.완료 시간의 임의의 고정 전력까지 확장할 수 있습니다.

3. 동일 또는 균일한 기계 수에 대한 가중 완료 시간의 합계 - Qm † ${\displaystyle w_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle C_{}}$ j \$displaystyle \sum w_{j} C_{j$로 표시됩니다.

(4) 동일하거나 균일한 수의 기계에서의 완료 시간의 합계 및 시간 의존적인 처리 시간:Qm time-dep${\displaystyle {}_{}}$ ${\displaystyle C_{}}$j \ $displaystyle \sum$ C_${j$이 값은 가중 완료 시간의 합계에 대해서도 유지됩니다.

5. 임의의 수의 기계에서 공통의 납기일에 대한 가중치가 부여되어 있습니다.m † ${\displaystyle w_{}}$ ${\displaystyle c_{}}$ j${\displaystyle {}_{}}$\ $displaystyle$\$sum w$_ {$j$ } $C$_ { $j$ $。$

심플 다이내믹 프로그램

단순한 동적 프로그램은 위의 공식에 다음 구성 요소를 추가합니다.

• F와 같은 카디널리티의 필터링 함수의 집합 H.H의 각 함수h는_i 쌍(state, input)을 부울값에 매핑합니다.이 쌍으로 이행_i f를 활성화하여 유효한 상태가 될 경우에만 값이 "true"여야 합니다.
• 상태에 대한 부분 순서인 지배 관계(무관심, 모든 쌍이 비교 가능한 것은 아님)와 상태에 대한 총 사전 순서인 준지배 관계(유추 허용, 모든 쌍이 비교 가능)입니다.

원래의 DP는 다음과 같이 변경됩니다.

• S : = 초기 상태 집합으로 합니다₀.
• k = 1 ~ n 의 경우:
  • S_k : = {f_j(s,x_k) f_j in F, s in_k−1 S, h_j(s,x_k)=로 하자.True }, 여기서_j h는 전이 함수_j f에 대응하는 필터 함수입니다.
• 최소/최대 {g(s)의 S}을_n(를) 출력합니다.

문제가 다음 조건(상기 조건 1, 2, 3을 확장함)을 충족하면 자비라고 불립니다.

1. 근접성은 전환 기능을 통해 유지됩니다.임의의 r>1, F의 임의의 전이함수 f, 임의의 입력벡터 x 및 임의의 2개의 상태벡터에₁₂ 대해 다음이 유지됩니다.
   • s가 s에 (d,r₂)-근접하고₁ s 준근접일₂ 경우₁, (a) f₁(s,x)는 f₂(s,x)-근접하고 f(s₁₂,x) 또는 (b) f(s₁,x)가 f(s₂,x)를 지배한다.
   • s가₁ s를 지배하면₂ f(s₁,x)가 f(s₂,x)를 지배한다.
2. 근접성은 값 함수에 의해 유지됩니다.정수 G , 0(값 함수 g와 정도 벡터 d의 함수)이 존재하기 때문에 임의의 r>1 및 임의의 2개의 상태 벡터에₁₂ 대해 다음이 유지됩니다.
   • s가 (d,r)-s₂₂ 및 s₁ 준소수 s에 가까운 경우₁, g(s₁) r^G r · g(s₂)(최소화 문제에서), g(s₁) r^(-G) r · g(s₂)(최대화 문제에서)이다.
   • s가₁ s를 지배하면₂ g(s₁) ( g₂(s) (최소화 문제); g(s₁) g g(s₂) (최대화 문제)
3. 기술 조건(상기 외에):
   • 준우위 관계는 다항식 시간으로 결정될 수 있다.
4. 필터 기능의 조건:임의의 r>1, H의 임의의 필터 함수h, 임의의 입력 벡터x 및 임의의 2개의 상태 벡터에는₁₂ 다음이 유지됩니다.
   • s가₂ (d,r)-s에 가깝고 s의₁ 준거치₂ s이면₁ h(s₁,x) ≤ h(s₂,x)이다.
   • s가₁ s를 지배하면₂ h(s₁,x)) h(s₂,x)입니다.

모든 유익한 문제에 대해 동적 프로그램은 위의 것과 유사하게 FPTAS로 변환할 수 있으며, 두 가지 변경(굵은 글씨)이 있습니다.

• T : = S₀ = 초기 상태의 집합이라고 하자₀.
• k = 1 ~ n 의 경우:
  • U_k : = {f_j(s,x_k) f_j in F, s in_k−1 T, h_j(s,x_k) =True }, 여기서_j h는 전이 함수_j f에 대응하는 필터 함수입니다.
  • 하나 이상의 U_k 상태를 포함하는 각 r 상자에 대해 T : =를 U:의_k 잘린 복사본으로 하고_k U에 있는_k 다른 모든 요소를 준결합하는 단일 요소를 선택한 후 T에_k 삽입합니다.
• 최소/최대 {g(s)을 T 단위로_n 출력합니다.

예

위의 ^[6]정리에 의해 FPTAS를 갖는 자비로운 문제의 예를 몇 가지 소개합니다.

1. 0-1 배낭 문제는 자비롭다.여기 a=2가 있습니다. 각 입력은 2진수(가중치, 값)입니다.b=2인 DP가 있습니다. 각 상태는 인코딩됩니다(전류 중량, 전류 값).두 가지 전환 함수가 있습니다₂. f는 다음 입력 항목을 추가하는 것과 f는 추가하지 않는 것에 해당합니다₁.대응하는 필터 함수는 다음과₁ 같습니다.h는 다음 입력 항목의 무게가 최대 배낭 용량인지 확인합니다.h는₂ 항상 True를 반환합니다.값 함수 g는 s를 반환합니다₂.초기 상태 집합은 {(0,0)}입니다.정도 벡터는 (1,1)입니다.지배관계는 사소한 것이다.준우위관계는 가중치 좌표만을 비교한다. 즉, 준우위관계는 tiff₁ s t₁ t이다.이는 상태 t가 상태 s보다 가중치가 높을 경우 t와 s 사이의 근접성을 유지할 수 없다는 것을 의미합니다(예를 들어 s에는 후계자가 있고 t에는 대응하는 후계자가 없는 경우 등).비슷한 알고리즘이 앞서 이바라와 ^[7]김에 의해 제시되었다.이 FPTAS의 실행 시간은${\displaystyle }$^[8]${\displaystyle \mathrm{정수}}$에서 ${\displaystyle O}$(n${\displaystyle log\mathrm{}}$/ 1${\displaystyle }$/${\displaystyle 1}$ + ${\displaystyle {1\mathrm{}}^{}}$ /$)$ 4 )\style $O(n\log {1/\epsilon$}+$1/\epsilon$^{$4})$ 연산으로$$ $개선$할 수 있습니다.이 지수는 나중에 2.^[9]5로 개선되었다.

• 주의: 2가중치 배낭 문제에서는 각 항목에 2개의 무게와 1개의 값이 있으며, 목표는 총 무게의 제곱합이 배낭 용량 최대가 되도록 값을 최대화하는 것입니다: (${\displaystyle {\underset{k}{}}^{}}$ k${\displaystyle {\underset{}{}{1}_{}}^{}}$ ${\displaystyle {\underset{}{K}{}_{}}^{}}$w${\displaystyle {{}_{}}^{}{\mathrm{}}^{}{}^{}}$,${\displaystyle {}^{}}$k )${\displaystyle {\underset{}{}}^{}}$2 + (${\displaystyle {{}_{}\underset{}{k}}^{}}$ k$$ ${\displaystyle {\underset{}{}{}_{}}^{}}$ ${\displaystyle {{w\mathrm{}}_{}}^{}}$2 , ${\displaystyle {\mathrm{}}^{}}$ )$style$ W $display$ \ $k$\ $in left$ \ sum \ sum$오른쪽)^{2}+\left(\sum$ _${k\in$ K$}w_{$2,$k}\right)^{2}\leq$W$\}.$ 각 상태(현재 가중치 1, 현재 가중치 2, 값)에 해당하는 유사한 DP를 사용하여 해결할 수 있습니다.준우위 관계는 다음과 같이 수정해야 한다. s 준우위 t iff (s₁² + s₂²) † (t₁² + t₂²)그러나 위의 조건 1에 위반된다.준지배력은 전이함수(예를 들어 상태 (2,2,..) 준지배(1,3,..)에 의해 보존되지 않지만, 입력(2,0,..)을 두 상태에 더하면 결과 (4,2,..)가 준지배(3,3,..)가 준지배적이지 않다.그래서 그 정리는 사용할 수 없다.실제로 이 문제는 P=NP가 아닌 한 FPTAS를 가지고 있지 않다.2차원 배낭 문제도 마찬가지다.다중 서브셋합 문제에 대해서도 마찬가지입니다.준우위관계는 다음과 같아야 합니다.s 준우위관계는 t ifff max(ss_1,2) ( max(tt_1,2)이지만 위와 같은 예에 의해 전이에 의해 보존되지 않습니다.

2. 1 ${\displaystyle {}_{}}$ w ${\displaystyle {}_{}{}_{}}$ \ $displaystyle \sum$ w_${j}$로 표시된 1대의 기계로 지각 작업의 가중치 최소화 또는 초기 작업의 가중치 최대화$U_{j$

3. 지각 작업의 가중치를 최소화하는 배치 스케줄링 : 1 batch${\displaystyle {}_{}}$ w ${\displaystyle {}_{}{}_{}}$ U$$ \ $displaystyle \sum$ w_${j}$$U_{j$

4. 1대의 기계로 작업 악화의 시간: 1대의 ${\displaystyle 악화}$의 최대 $(\$ C_${j$

5. ${\displaystyle {}_{}}$의 기계에서의 합계 레이트 작업: 1 † V$$ \ $displaystyle$\ $sum$ V _ { $j$}$$。

6. 1대의 기계에서의 가중치 레이트 작업의 합계: 1 ${\displaystyle {}_{}{}_{}}$ ${\displaystyle V_{}}$j \$displaystyle \sum w_{j}V_{j$

비예시

상기의 결과에도 불구하고 사용할 수 없는 경우가 있습니다.

1. Total terdentity 문제1 ${\displaystyle {}_{}}$ ${\displaystyle T_{}}$ j$$\ $displaystyle \sum$ T_${j$$$, , 、 Lawler의^[10] 다이내믹 프로그래밍 공식에서는 구 상태 공간의 모든 상태를 B회 갱신해야 합니다.여기서 B는 X(최대 입력 크기)의 순서입니다.경제적 로트사이징을 ^[11]위한 민주당도 마찬가지다.이 경우 F의 전이함수는 로그(X)의 지수함수인 B이므로 두 번째 기술조건을 위반한다.상태 트리밍 기법은 유용하지 않지만 다른 기법인 입력 ^[12][13]라운딩이 FPTAS 설계에 사용되었습니다.

2. 분산 최소화 문제 1 C ${\displaystyle T}$ {$displaystyle$ CTV$\}$에서 목적 함수는 g${\displaystyle }$(${\displaystyle s}$ ) ${\displaystyle =}$ ${\displaystyle {s\mathrm{}}_{}}$5${\displaystyle }$- ( ${\displaystyle {s\mathrm{}}^{}{}_{}}$4 - ${\displaystyle {}_{}{}^{}}$)${\displaystyle {}^{}}$2 /$$ ( \ $display$ g ( s ) =$s$_ { $5$} - ( s _ { $4$} - ( s _ { 4 } - $s$_ { $3$)^2} $/ n$ 이므로 정리는 사용할 수 없다.그러나 FPTAS를 ^[14][15]설계하기 위해 다른 기술이 사용되었습니다.

FPTAS에 관한 기타 문제

• 배낭 문제 ^[16][17]및 일부 변형:
  • 0-1 배낭 ^[18]문제
  • 제한 없는 배낭 문제.^[19]
  • 델타 모듈러 ^[20]구속조건의 다차원 배낭 문제.
  • 다목적 0-1 배낭 ^[21]문제
  • 파라메트릭 배낭 ^[22]문제
  • 대칭 2차 배낭 문제.^[23]
• Count-subset-sum(#SubsetSum) - 최대 ^[24]C의 개별 서브셋 수를 검색합니다.
• 제한된 최단 경로: 그래프에서 두 노드 간의 최소 비용 경로를 찾습니다. 지연 제약 ^[25]조건이 적용됩니다.
• 최단 경로 및 비선형 목표.^[26]
• 엣지-커버를 카운트 중.^[27]
• 치수가 ^[28]고정된 벡터 부분 집합 검색 문제.

「 」를 참조해 주세요.

• FPTAS를 허용하는 "진화 동적 프로그램"도 진화 ^[29]알고리즘을 허용합니다.

레퍼런스

외부 링크

• 복잡성 동물원: FPTAS