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

完全多項式時間近似スキーム (FPTAS) は、関数の問題、特に最適化の問題に対する近似解を見つけるためのアルゴリズムです。FPTAS は、問題のインスタンスとパラメーター ε > 0 を入力として受け取ります。出力として、正しい値の少なくとも 倍、最大で正しい値の 倍 の値を返します。${\displaystyle 1-\varepsilon }$${\displaystyle 1+\varepsilon }$

最適化問題の文脈では、正しい値は最適解の値であると理解されており、FPTAS は有効な解 (解の値だけではなく) を生成する必要があることがしばしば暗示されています。問題が自己還元性を持っていると仮定すると、値を返すことと、その値を持つ解を見つけることは同等です。

重要なのは、FPTAS の実行時間は問題のサイズと 1/ε の多項式であるということです。これは、一般的な多項式時間近似スキーム(PTAS) とは対照的です。一般的な PTAS の実行時間は、特定の ε ごとに問題のサイズの多項式ですが、1/ε では指数関数的になる可能性があります。^[1]

FPTASという用語は、FPTASを持つ問題のクラスを指すためにも使用される。FPTASはPTASのサブセットであり、P = NPでない限り、厳密なサブセットである。^[2]

FPTASにおけるすべての問題は、標準的なパラメータ化に関して固定パラメータで扱うことができる。 ^[3]

多項式的に制限された目的関数を持つ任意の強くNP困難な最適化問題は、P = NPでない限りFPTASを持つことはできません。 ^[4]しかし、逆は失敗します。たとえば、PがNPと等しくない場合、 2つの制約を持つナップサックは強くNP困難ではありませんが、最適な目的関数が多項式に制限されている場合でもFPTASはありません。^[5]

Woeginger ^[6]は、ある種の動的プログラムをFPTASに変換するための一般的なスキームを提示した。

このスキームは、入力が次のように定義される最適化問題を処理します。

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

この問題には、状態を使用する動的計画法 (DP) アルゴリズムがあると仮定します。各状態は、入力に依存しない非負の整数で構成されるベクトルです。DP はnステップで動作します。各ステップiで、入力x _{i を}処理し、状態のセット S i を構築します。_各状態は、入力x ₁、...、x _{i を}使用して、問題の部分的な解をエンコードします。DP のコンポーネントは次のとおりです。 ${\displaystyle b}$${\displaystyle b}$

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

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

• S ₀  := 初期状態の集合とします。
• k = 1 からnまでの場合、次の操作を実行します。
  • S _k  := { f ( s , x _k ) | f in F , s in S _{k −1} }とします。
• 最小/最大{g(s) | s in S _n }を出力します。

DP の実行時間は、可能な状態の数に比例します。一般に、この数は入力問題のサイズに対して指数関数的になります。つまり、O( n V ^b ) になります。ここで、V は状態に現れる最大の整数です。V が O( X ) の場合、実行時間は O( n X ^b ) になります。これは、問題のサイズに対して指数関数的であるため、疑似多項式時間でしかありません。問題のサイズは O(log X ) です。

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

これを形式化するために、問題には負でない整数ベクトルd = ( d ₁ ,..., d _b ) があり、これを問題の次数ベクトルと呼ぶと仮定します。すべての実数r >1 について、1,..., b内の各座標jに対して次の式が成り立つとき、 2 つの状態ベクトルs ₁、s ₂は(d,r) 近いと言えます。 (特に、あるjに対してd _j =0 である場合、)。 ${\displaystyle r^{-d_{j}}\cdot s_{1,j}\leq s_{2,j}\leq r^{d_{j}}\cdot s_{1,j}}$${\displaystyle 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番目の座標をf _j (s,x)で表します。このf _{j は}、 b + a変数の整数関数として考えることができます。このようなf _{j は}すべて非負の係数を持つ多項式であるとします。s =(z ^d1 ,...,z ^db ) およびx =(1,...,1) を代入して、これを単一変数zの多項式に変換します。結果として得られる多項式の z の次数が d j 以下であれば、条件₁は満たされます。
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 _{1 は}条件 3 の多項式です (状態ベクトルに現れる可能性のあるすべての値の ln の上限)。なので、これは入力のサイズと の多項式であることに注意してください。 また、なので、 P ₁の定義により、状態ベクトルに現れる可能性のあるすべての整数は [0, r ^L ] の範囲内にあります。${\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})}}$
• 範囲[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ボックスに分割します。_次数dk≥1の各座標kは上記のL+1個の間隔に分割されます。dk=0の各座標は_P2 ( n _, log(X))個のシングルトン間隔、つまり座標kの各可能な値に対する間隔に分割されます(ここで、P2は上記の条件₃からの多項式です)。
  • すべての可能な状態は、正確に 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 と同様に実行されますが、各ステップで状態セットを、各rボックスに正確に 1 つの状態が含まれる小さなセットT _kにトリミングします。FPTAS のアルゴリズムは次のとおりです。

• T ₀  := S ₀ = 初期状態の集合とします。
• k = 1 からnまでの場合、次の操作を実行します。
  • U _k  := { f ( s , x _k ) | f in F , s in T _{k −1} }とします。
  • T _k := U _k のトリミングされたコピーとします。U _kの 1 つ以上の状態を含む各 r ボックスに対して、 T kに_正​​確に 1 つの状態を保持します。
• 最小/最大 {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] : Lem.3.3}

⁰ ,..., nの すべてのステップkについて、 S _kのすべての状態s _sに対して、 s _sに( d , rk ) 近いT _kの状態s _tが存在します。

証明はkに関する帰納法による。k =0 のとき、 T _k = S _kであり、すべての状態は自身に ( d , 1) 近接している。 k -1について補題が成り立つと仮定する。 S _kのすべての状態s _sについて、s _{s- を}S _k-1におけるその先行状態の 1 つとし、 f​​ ( _{s s} − _, x ) = s _sとする。帰納法の仮定により、 T _k-1には状態s _t-が存在し、これはs _{s −に (} d , r ^k-1 ) 近接している。近接性は遷移によって保存されるため (上記の条件 1)、f ( s _{t −} , x ) はf ( s _{s −} , x )= s _sに( d , r ^k-1 ) 近接している。このf ( s _{t −} , x ) はU _kにある。トリミング後、T _kにはf( _st- ,x)に( d , r _{)-近い状態 st}があります。このst_はs _sに( d , rk ⁾ -近いです。

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

ここに、上記の定理によりFPTASが成立する極めて善意の問題の例をいくつか挙げる。^[6]

1.最大合計を最小化することを目標とする多元数分割(同等の同一マシン スケジューリング) は、極めて善良です。ここで、 a = 1 (入力は整数)、b = ビンの数 (固定とみなされます) です。各状態は、bビンの合計を表すb整数のベクトルです。 b個の関数があります。各関数jは、次の入力をビンjに挿入することを表します。関数g ( s ) は、 sの最大要素を選択します。S ₀ = {(0,...,0)}。極めて善良であるための条件は、次数ベクトルd =(1,...,1) およびG =1 で満たされます。結果は、マシン数が固定されている場合 ( rボックスの数Rがbの指数関数であるため、これが必要です) は常に、均一マシン スケジューリングおよび無関係マシン スケジューリングに拡張されます。 Pm||または Qm||または Rm||で示されます。 ${\displaystyle \max C_{j}}$${\displaystyle \max C_{j}}$${\displaystyle \max C_{j}}$

• 注: 特別なケースb =2 を考えてみましょう。この場合は、2 つの部分の合計の差の 2 乗を最小化することが目標です。同じ DP を使用できますが、今回は値関数g ( s ) = ( s ₁ - s ₂ ) ²を使用します。ここで、条件 2 に違反します。つまり、状態 ( s ₁、s ₁ ) と ( s ₁、s _{2 ) は (} d,r ) 近い可能性がありますが、g ( s ₁、s ₁ ) = 0 であるのに対し、g ( s ₁、s ₂ ) > 0 です。したがって、上記の定理は適用できません。実際、P=NP でない限り、この問題には FPTAS がありません。FPTAS を使用すると、最適値が 0 かどうかを多項式で判断できるためです。

2. 同一または均一なマシンの任意の固定数におけるジョブ完了時間の 3 乗の合計 (後者は Qm|| で表されます) は、 a =1、b =3、d=(1,1,3)の場合に ex-benevolent です。これは、完了時間の任意の固定乗に拡張できます。 ${\displaystyle \sum C_{j}^{3}}$

3. 同一または均一なマシンの固定数における加重完了時間の合計。後者はQm||で表されます。 ${\displaystyle \sum w_{j}C_{j}}$

4. 時間に依存する処理時間を持つ、任意の固定数の同一または均一なマシンでの完了時間の合計: Qm|time-dep| 。これは、完了時間の加重合計に対しても当てはまります。 ${\displaystyle \sum C_{j}}$

5. 任意の固定数のマシンにおける共通納期に関する加重早遅刻: m|| 。 ${\displaystyle \sum w_{j}|C_{j}|}$

単純な動的プログラムでは、上記の定式化に次のコンポーネントが追加されます。

• 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に対応するフィルタ関数です。
• 最小/最大{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 ≥ 0 (価値関数gと次数ベクトルdの関数) が存在し、任意のr >1 および任意の 2 つの状態ベクトルs ₁、s ₂に対して、次の式が成り立ちます。
   • s _{1 が}s ₂に( d, r ) 近接しており、s _{1 が}s _{2 を}準優位とする場合、g ( s 1 ) _≤ r G ^· g ( s 2 ₎ (最小化問題の場合)、 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 1 _, x ) ≥ h ( s ₂ , x )です。
   • s _{1 が}s ₂より優勢である場合、 h ( s ₁ , x ) ≥ h ( s ₂ , x )です。

すべての善意の問題に対して、動的プログラムは、2 つの変更 (太字) を加えることで、上記と同様に FPTAS に変換できます。

• 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に挿入します。
• 最小/最大 {g(s) | s in T _n } を出力します。

ここに、上記の定理によりFPTASとなる善意の問題の例をいくつか挙げます。^[6]

1. 0-1ナップサック問題は善意の問題です。ここで、a =2 です。各入力は 2 ベクトル (重み、値) です。b =2 の DP があります。各状態は (現在の重み、現在の値) をエンコードします。2 つの遷移関数があります。f _{1 は}次の入力項目の追加に対応し、f _{2 は}追加しないことに対応します。対応するフィルター関数は次のとおりです。h _{1 は}、次の入力項目の重みがナップサックの容量以下であることを確認します。 h _{2 は}常に True を返します。値関数g ( s ) はs ₂を返します。初期状態セットは {(0,0)} です。次数ベクトルは (1,1) です。優位関係は自明です。準優位関係は重み座標のみを比較します。sはt を準優位とする場合、s ₁ ≤ t ₁となります。この意味は、状態t の重みが状態sよりも高い場合、遷移関数はtとsの近接性を維持しなくてもよいということです（たとえば、s には後続があり、t には対応する後続がない可能性があります）。同様のアルゴリズムは、以前に Ibarra と Kim によって発表されました。^[7]この FPTAS の実行時間は、整数演算にまで改善できます。^[8]指数は後に 2.5 に改善されました。^[9]${\displaystyle O(n\log {1/\epsilon }+1/\epsilon ^{4})}$

• 注: 2 重みナップザック問題を考えます。ここで、各アイテムには 2 つの重みと 1 つの値があり、合計重みの二乗の合計がナップザックの容量以下になる ように値を最大化することが目標です。同様の DP を使用してこれを解くことができます。ここで、各状態は (現在の重み 1、現在の重み 2、値) です。準優位関係は、次のように変更する必要があります。s は、( s 1 ₂ ⁺ s 2 ₂ ⁾ ≤ ( t ₁ ² + t ₂ ^{2 ) の場合に}t を準優位にします。ただし、これは上記の条件 1 に違反します。準優位は遷移関数によって保持されません [たとえば、状態 (2,2,..) は (1,3,..) を準優位にします]。しかし、両方の状態に入力 (2,0,..) を追加した後、結果 (4,2,..) は (3,3,..) を準優位にしません。したがって、定理は使用できません。実際、この問題は P = NP でない限り FPTAS を持ちません。2 次元ナップサック問題でも同じことが言えます。多重サブセットの合計問題でも同じことが言えます。準優位関係は、次のようになります。max( s _1, s ₂ ) ≤ max( t _1, t _{2 ) の場合に}s がt を準優位にするが、上記と同じ例により、遷移によって保持されません。${\displaystyle \left(\sum _{k\in K}w_{1,k}\right)^{2}+\left(\sum _{k\in K}w_{2,k}\right)^{2}\leq W}$

2. 単一のマシン上で、遅れたジョブの加重数を最小化するか、早めに到着するジョブの加重数を最大化します。1|| と表記します。 ${\displaystyle \sum w_{j}U_{j}}$

3. 遅れたジョブの加重数を最小化するためのバッチ スケジューリング: 1|batch| 。 ${\displaystyle \sum w_{j}U_{j}}$

4. 単一マシン上での劣化ジョブのメイクスパン: 1|劣化| 。 ${\displaystyle \max C_{j}}$

5. 単一マシンでの合計遅延作業数: 1|| 。 ${\displaystyle \sum V_{j}}$

6. 単一マシン上の加重遅延作業の合計: 1|| 。 ${\displaystyle \sum w_{j}V_{j}}$

上記の結果は一般性があるものの、使用できないケースもあります。

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

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

FPTAS が役に立つかもしれない別の種類の問題は、ある実数を近似する有理数を見つけることです。たとえば、無限級数 を考えてみましょう。その和は無理数です。これを有理数で近似するには、ある有限のkに対して最初のk要素の和を計算します。近似の誤差は約 であることがわかります。したがって、ε の誤差を得るには約 個の要素が必要であり、これは FPTAS です。この特定の和は、O(log(ε)) 個の要素のみを必要とする別の和で表すことができることに注意してください。したがって、和は実際には ε のエンコード長で多項式時間で近似できます。^{[16] : 35、Sec.1}${\displaystyle \sum _{i=1}^{\infty }{\frac {1}{i^{3}}}}$${\displaystyle {\frac {1}{2k^{2}}}}$${\displaystyle {\sqrt {\frac {1}{2\epsilon }}}}$

• ナップサック問題[ 17 ^{] [18]}およびその変種:
  • 0-1ナップサック問題^[19]
  • 無限ナップサック問題^[20]
  • デルタモジュラー制約を伴う多次元ナップサック問題。^[21]
  • 多目的0-1ナップサック問題^[22]
  • パラメトリックナップサック問題^[23]
  • 対称二次ナップサック問題^[24]
• Count-subset-sum (# SubsetSum ) - 合計が最大でCになる異なるサブセットの数を見つける。^[25]
• 制限付き最短経路：遅延制約の下でグラフ内の2つのノード間の最小コスト経路を見つけること。^[26]
• 最短経路と非線形目標^[27]
• エッジカバーを数える。^[28]
• 次元が固定されたベクトル部分集合探索問題。^[29]

• FPTASを認める「善意の動的プログラム」は進化的アルゴリズムも認める。^[30]

• 複雑性動物園: FPTAS