完全多項式時間近似スキーム

この方式は、入力が以下のように定義される最適化問題を扱います。

• 入力はn個のベクトルx ₁ ,..., x _nで構成されます。
• 各入力ベクトルはいくつかの${\displaystyle a}$非負整数、${\displaystyle a}$入力内容によって異なる場合があります。
• 入力ベクトルのすべての成分はバイナリでエンコードされます。したがって、問題のサイズはO( n + log( X ))となります。ここで、Xはすべてのベクトルのすべての成分の合計です。

この問題には、状態を用いた動的計画法（DP）アルゴリズムが存在すると仮定する。各状態は、いくつかの要素からなるベクトルである。${\displaystyle b}$非負整数、${\displaystyle b}$入力に依存しない。DPはnステップで動作する。各ステップiにおいて、入力x _iを処理し、状態の集合S _iを構築する。各状態は、入力x ₁ ,..., x _iを使用して、問題の部分解を符号化する。DPの構成要素は以下のとおりである。

• 初期状態の集合S ₀。
• 遷移関数の集合F。Fに含まれる各関数fは、 (状態、入力)のペアを新しい状態にマッピングする。
• 状態をその値にマッピングする目的関数g。

DPのアルゴリズムは次のとおりです。

• S ₀  := 初期状態の集合とする。
• k = 1 からn まで、以下を実行する。
  • S _k  := { f ( s , x _k ) | f ∈ F , s ∈ S _{k −1} }とする
• 出力はmin/max {g(s) | s in S _n }です。

DP の実行時間は、可能な状態の数に対して線形です。一般に、この数は入力問題のサイズに対して指数関数的になる可能性があります。つまり、O(nVb) になることがあります^。ここで、Vは状態に存在する最大の整数です。V が O( X )の場合、実行時間は O( nXb ) になりますが、これは問題のサイズ (O(log ^X ) )に対して指数関数的であるため、擬似多項式時間にすぎません。

計算量を多項式にする方法は、状態空間をトリミングすることです。つまり、各ステップですべての可能な状態を保持するのではなく、状態のサブセットのみを保持し、他の状態に「十分近い」状態を削除します。特定の条件下では、このトリミングを目的関数値を大きく変化させることなく行うことができます。

これを形式化するために、対象となる問題には非負の整数ベクトルd = ( d ₁ ,..., d _b ) があり、これを問題の次数ベクトルと呼ぶと仮定します。任意の実数r >1 に対して、2 つの状態ベクトルs ₁、s ₂が(d,r) 近接であるとは、 1,..., bの各座標jについて、次の条件が満たされる場合をいいます。 $\displaystyle r^{-d_{j}}\cdot s_{1,j}\leq s_{2,j}\leq r^{d_{j}}\cdot s_{1,j}}$（特に、あるjに対してd _j =0の場合、$s_{1,j}=s_{2,j}}$)

問題が極めて善意に満ちていると言えるのは、以下の3つの条件を満たす場合である。

1. 遷移関数によって近接性が維持されます。任意のr > 1、 F内の任意の遷移関数f、任意の入力ベクトルx、および任意の 2 つの状態ベクトルs ₁、s ₂に対して、次のことが成り立ちます。s 1 が s 2 に対して ( d,r ) 近い場合、_f ( _s 1 、 x )はf ( _s 2 、x )に対して₍ d , r )近い。
   • この十分条件は次のように確認できます。F のすべての関数 f ( s , x ) と、1,..., b のすべての座標 j について、f j ( s , x )をfのj_番目の座標とします。このf _{j は、} b + a 個の変数に関する整数関数と見なすことができます。このようなf _{j は}すべて非負の係数を持つ多項式であると仮定します。s =(z ^d1 ,...,z ^db ) およびx = (1,...,1) を代入して、これを単一変数zの多項式に変換します。結果として得られるzに関する多項式の次数がd _j以下であれば、条件 1 が満たされます。
2. 近接性は価値関数によって保持されます。ある整数G ≥ 0 (これは価値関数gと次数ベクトルdの関数です) が存在し、任意のr > 1 および任意の 2 つの状態ベクトルs ₁、s ₂に対して、次のことが成り立ちます。s 1_がs ₂に対して( d,r )-近い場合、次のようになります。g ( s ₁ ) ≤ r ^G · g ( s ₂ ) (最小化問題の場合)、 g ( s ₁ ) ≥ r ^(-G) · g ( s ₂ ) (最大化問題の場合)。
   • そのための十分条件は、関数gが（ b個の変数を持つ）非負の係数を持つ多項式関数であることである。
3. 技術条件：
   • Fに含まれるすべての遷移関数fと値関数gは、多項式時間で評価できる。
   • 遷移関数の数 | F | はnと log( X ) の多項式です。
   • 初期状態の集合S _0は、 nと log( X )の多項式時間で計算できます。
   • V _{j を、}ある状態において座標jに現れる可能性のあるすべての値の集合とする。このとき、 V _jのすべての値のln は、高々多項式 P ₁ (n,log(X)) となる。
   • d _j =0の場合、 V _jの濃度は 最大で多項式 P ₂ ( n ,log( X )) になります。

極めて善意的な問題であれば、動的計画法をFPTASに変換できます。定義：

• ${\displaystyle \epsilon }$ := 必要な近似比。
• ${\displaystyle r:=1+{\frac {\epsilon }{2Gn}}}$ここで、Gは条件2の定数である。$\displaystyle \frac {1}{\ln {r}}}\leq 1+{\frac {2Gn}{\epsilon }}}$。
• ${\displaystyle L:=\left\lceil {\frac {P_{1}(n,\log(X))}{\ln(r)}}\right\rceil }$ここで、P ₁は条件 3 の多項式 (状態ベクトルに現れる可能性のあるすべての値の ln の上限) です。${\displaystyle L\leq \left\lceil \left(1+{\frac {2Gn}{\epsilon }}\right)P_{1}(n,\log {X})\right\rceil }$入力サイズと の多項式である${\displaystyle 1/\epsilon }$。 また、${\displaystyle r^{L}=e^{\ln {r}}\cdot L\geq e^{P_{1}(n,\log {x})}}$したがって、 P ₁の定義により、状態ベクトルに現れる可能性のあるすべての整数は [0, r ^L ] の範囲内になります。
• 範囲 [0, r ^L ] をL + 1個のr個の区間に分割します。${\displaystyle I_{0}=[0];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 k = 0 の各座標は、P ₂ ( n ,log( X )) 個の単一区間に分割されます。これは_、座標kの可能な値ごとに 1 つの区間になります( P ₂は、上記の条件 3 の多項式です)。
  • すべての可能な状態は、ちょうど 1 つのrボックスに含まれていることに注意してください。2 つの状態が同じrボックス内にある場合、それらは ( d , r )-近い状態です。
• ${\displaystyle R:=(L+1+P_{2}(n,\log {X}))^{b}}$。
  • rボックスの数は最大でRであることに注意してください。b は固定定数であるため、このRは入力サイズと の多項式になります。${\displaystyle 1/\epsilon }$。

FPTASはDPと同様に動作しますが、各ステップで状態セットをより小さなセットT _kにトリミングし、各rボックスにちょうど1つの状態が含まれるようにします。FPTASのアルゴリズムは次のとおりです。

• T ₀  := S ₀ = 初期状態の集合とする。
• k = 1 からn まで、以下を実行する。
  • U _k  := { f ( s , x _k ) | f ∈ F , s ∈ T _{k −1} }とする
  • T _k := U _kのトリミングされ たコピーとする。U _kの 1 つ以上の状態を含む各r -ボックスに対して、 T _kにはちょうど 1 つの状態を保持する。
• 出力は min/max {g(s) | s in T _n } です。

FPTAS の実行時間は、各T _iにおける可能な状態の総数に関する多項式であり、これは最大でrボックスの総数であり、これは最大でRであり、これはn、log( X )に関する多項式である。${\displaystyle 1/\epsilon }$。

U _kの 各状態s _uに対して、その部分集合T _kには、 s _uに (d,r)-近い状態s _{t が}少なくとも 1 つ含まれていることに注意してください。また、各U _{k は}、元の (トリミングされていない) DP のS _kの部分集合です。FPTAS の正当性を証明するための主な補題は次のとおりです。^{[ 6 ] :補題 3.3}

0,..., nの 各ステップkに対して、 S _kの各状態s _sに対して、 s _sに( d , r ^k )-近い状態s _tがT _kに存在する。

証明はkに関する帰納法による。k = 0 の場合、_{T k = S k となる。すべての状態はそれ自身に ( d ,1)-近い。補題が k -1 に対して成り立つと仮定する。S k}の_すべての状態_s sに対して、 s s-をS k - ₁のその_前任者_の1 つとすると、f ( s _{s −} , x )= s _sとなる。帰納法の仮定により、 T _k-1にはs _{s −}に( d , r ^k-1 )-近い状態s _t-が存在する。遷移によって近接性が保存されるため (上記の条件 1)、f ( s _{t −} , x ) はf ( s _{s −} , x )= s _sに ( d , r ^k-1 )-近い。このf ( s _{t −} , x ) はU _kに含まれる。トリミング後、T _kにはf(s _t- ,x)に( d , r )-近い状態s _tが存在する。このs _tはs _sに( d , r ^k )-近い。

ここで、 S _n内の状態s ^*を考えます。これは最適解 (つまり、g ( s* )=OPT) に対応します。上記の補題により、T _n内にs ^*に( d , r ⁿ )-近い状態t *が存在します。近接性は価値関数によって保存されるため、最大化問題ではg (t*) ≥ r ^(-Gn) · g ( s* ) となります。rの定義により、${\displaystyle r^{-Gn}\geq (1-\epsilon )}$。 それで${\displaystyle g(t^{*})\geq (1-\epsilon )\cdot OPT}$同様の議論は最小化問題にも当てはまる。

単純な動的プログラムは、上記の定式化に以下の要素を追加します。

• Fと同じ要素数を持つフィルタリング関数の集合H 。H内の各関数h _iは、ペア (状態、入力) をブール値にマッピングします。このペアに対して遷移f _iをアクティブにすると有効な状態になる場合に限り、値は「true」になります。
• 優位関係とは、状態に関する部分順序（無差別はなく、すべてのペアが比較可能であるとは限らない）であり、準優位関係とは、状態に関する全前順序（無差別が許容され、すべてのペアが比較可能である）である。

元のDPは以下のように変更されます。

• S ₀  := 初期状態の集合とする。
• k = 1 からn まで、以下を実行する。
  • S _k  := { f _j ( s , x _k ) | f _j in F , s in S _{k −1} , h _j ( s , x _k )=True } とする。ここでh _jは遷移関数f _jに対応するフィルタ関数である。
• 出力はmin/max {g(s) | s in S _n }です。

以下の条件を満たす場合、その問題は善意の問題と呼ばれます（上記の条件1、2、3を拡張したものです）。

1. 遷移関数によって近接性が維持されます。任意のr > 1、 F内の任意の遷移関数f、任意の入力ベクトルx、および任意の 2 つの状態ベクトルs ₁、s ₂に対して、以下が成り立ちます。
   • s _1がs ₂に( d,r )-近く、かつs _{1 が}s _{2 を}準支配する場合、(a) f ( s ₁ , x ) はf ( s ₂ ,x ) に( d,r )-近く、かつf ( s ₁ , x )がf ( s ₂ ,x )を準支配するか、または (b) f ( s ₁ , x ) がf ( s ₂ ,x ) を支配するかのいずれかである。
   • s _{1 が}s ₂を支配する場合、f ( s ₁ , x ) はf ( s ₂ ,x ) を支配する。
2. 近接性は価値関数によって保持されます。価値関数gと次数ベクトルdの関数である整数G ≥ 0 が存在し、任意のr > 1 および任意の 2 つの状態ベクトルs ₁、s ₂に対して、次のことが成り立ちます。
   • s _1がs ₂に( d,r )-近接であり、かつ s _{1 が}s _{2 を}準支配する場合すると、次のようになります。g ( s ₁ ) ≤ r ^G · g ( s ₂ ) (最小化問題の場合)、 g ( s ₁ ) ≥ r ^(-G) · g ( s ₂ ) (最大化問題の場合)。
   • s _{1 が}s ₂を支配する場合、g ( s ₁ ) ≤ g ( s ₂ ) (最小化問題の場合)、 g ( s ₁ ) ≥ g ( s ₂ ) (最大化問題の場合) となります。
3. 技術条件（上記に加えて）：
   • 準優位関係は多項式時間で判定できる。
4. フィルタ関数に関する条件：任意のr > 1、任意のフィルタ関数h ∈ H、任意の入力ベクトルx、および任意の 2 つの状態ベクトルs ₁、s ₂に対して、以下が成り立つ：
   • s _1がs ₂に( d,r )-近い 場合、かつs _{1 が}s _{2 を}準支配する場合、h ( s ₁ , x ) ≥ h ( s ₂ , x )となります。
   • s _{1 が}s ₂を支配する場合、h ( s ₁ , x ) ≥ h ( s ₂ , x ) となります。

あらゆる善意の問題に対して、動的計画法は、上記と同様のFPTASに変換できますが、2つの変更点があります（太字部分）。

• T ₀  := S ₀ = 初期状態の集合とする。
• k = 1 からn まで、以下を実行する。
  • U _k  := { f _j ( s , x _k ) | f _j in F , s in T _{k −1} , h _j ( s , x _k )=True }とする。ここでh _jは遷移関数f _jに対応するフィルタ関数である。
  • T _k := U _k のトリミングされたコピーとする。U _kの 1 つ以上の状態を含む各r -ボックスについて、 U _k内の他のすべての要素を準支配する単一の要素を選択し、それをT _kに挿入する。
• 出力は min/max {g(s) | s in T _n } です。

上記の結果は一般的に当てはまるものの、適用できない場合もある。

1. 総遅延問題 1||${\displaystyle \sum T_{j}}$^{Lawler [ 10 ]}の動的計画法の定式化では、古い状態空間のすべての状態をB回更新する必要があります。ここで、BはX (最大入力サイズ)のオーダーです。経済的ロットサイズ決定のための DP についても同様です。^{[ 11 ]}これらの場合、 Fの遷移関数の数はBであり、これは log( X ) に対して指数関数的であるため、2 番目の技術的条件が満たされません。状態トリミング技術は役に立ちませんが、別の技術である入力丸めが FPTAS の設計に使用されています。^{[ 12 ] [ 13 ]}

2. 分散最小化問題 1||${\displaystyle CTV}$目的関数は ${\displaystyle g(s)=s_{5}-(s_{4}-s_{3})^{2}/n}$これは条件2に違反するため、定理は使用できません。しかし、FPTASを設計するためにさまざまな手法が使用されています。^{[ 14 ] [ 15 ]}