近似アルゴリズム

コンピュータサイエンスとオペレーションズリサーチにおいて、近似アルゴリズムは、最適化問題（特にNP困難な問題）の近似解を、返される解と最適解との距離が証明可能な保証付きで見つける効率的な アルゴリズムである。 ^{[1]近似アルゴリズムは、広く信じられている}P ≠ NP予想の結果として、理論コンピュータサイエンスの分野で自然に生まれた。この予想によれば、幅広いクラスの最適化問題は、多項式時間で正確に解くことはできない。そのため、近似アルゴリズムの分野では、そのような問題に対する最適解を多項式時間でどれだけ近似できるかを理解しようとする。ほとんどの場合、そのようなアルゴリズムの保証は、近似比または近似係数として表現される乗法的なものである。つまり、最適解は常に、返される解の（事前に決められた）乗法係数以内であることが保証される。ただし、返される解の品質について加法的な保証を提供する近似アルゴリズムも数多く存在する。両方を提供する近似アルゴリズムの注目すべき例としては、無関係な並列マシン上のスケジューリングのためのLenstra、Shmoys、Tardos ^[2]の古典的な近似アルゴリズムがあります。

近似アルゴリズムの設計と分析には、最悪の場合に返される解の品質を証明する数学的証明が不可欠です。 ^[1]この点が、アニーリングや遺伝的アルゴリズムなどのヒューリスティックとの違いです。アニーリングや遺伝的アルゴリズムは、いくつかの入力に対してかなり良い解を見つけますが、その解がいつ成功するか失敗するかについては、最初から明確な指標を提供しません。

理論計算機科学では、特定の有名な最適化問題を近似できる限界をより深く理解することに関心が集まっています。たとえば、計算機科学における長年の未解決の問題の 1 つは、Agrawal らによる Steiner Forest 問題に対する 2 近似を上回るアルゴリズムがあるかどうかを判断することです。^[3]近似可能性の観点から難しい最適化問題を理解したいという欲求は、驚くべき数学的つながりの発見と、難しい最適化問題のアルゴリズムを設計するための広く適用可能な手法によって動機付けられています。前者のよく知られた例の 1 つは、最大カットのGoemans-Williamson アルゴリズムで、高次元幾何学を使用してグラフ理論の問題を解きます。^[4]

近似アルゴリズムの簡単な例としては、最小頂点カバー問題が挙げられます。このアルゴリズムの目的は、入力グラフのすべての辺に少なくとも 1 つの選択された頂点が含まれるように、最小の頂点セットを選択することです。頂点カバーを見つける方法の 1 つは、次のプロセスを繰り返すことです。カバーされていない辺を見つけ、その両端をカバーに追加し、いずれかの頂点に接するすべての辺をグラフから削除します。入力グラフの頂点カバーは、プロセスで考慮された各辺をカバーするために個別の頂点を使用する必要があるため (マッチングを形成するため)、生成される頂点カバーは最大で最適なものの 2 倍の大きさになります。言い換えると、これは近似係数が 2 の定数係数近似アルゴリズムです。最近のユニーク ゲーム予想では、この係数は可能な限り最良のものです。^[5]

NP 困難問題は、近似可能性の点で大きく異なります。ナップサック問題など、いくつかの問題は、任意の固定 に対して乗法係数 内で近似できるため、最適値に任意に近い解が生成されます (このような近似アルゴリズムのファミリは、多項式時間近似スキームまたは PTAS と呼ばれます)。他の問題は、最大クリーク問題の場合のように、P = NPでない限り、任意の定数または多項式係数内で近似することはできません。したがって、近似アルゴリズムを研究する重要な利点は、 NP 完全性の理論によって提供されるものを超えて、さまざまな NP 困難問題の難しさのきめ細かい分類です。言い換えると、NP 完全問題は、正確な解の観点からは (多項式時間削減の下で) 互いに同等である可能性がありますが、対応する最適化問題は、近似解の観点からは非常に異なる動作をします。 ${\displaystyle 1+\epsilon }$${\displaystyle \epsilon >0}$

現在までに、近似アルゴリズムを設計するための確立された手法がいくつかあります。これには次のものが含まれます。

1. 貪欲アルゴリズム
2. ローカル検索
3. 列挙と動的計画法（パラメータ化された近似にもよく使用される）
4. 凸計画緩和法を解いて分数解を取得します。次に、この分数解を適切な丸めによって実行可能な解に変換します。一般的な緩和法には次のものがあります。
   • 線形計画法の緩和
   • 半正定値計画法の緩和
5. プライマル・デュアル法
6. デュアルフィッティング
7. 問題を何らかのメトリックに埋め込み、そのメトリックに基づいて問題を解決します。これはメトリック埋め込みとも呼ばれます。
8. ランダムサンプリングと、上記の方法と組み合わせた一般的なランダム性の使用。

近似アルゴリズムは常に、事前最悪ケース保証 (加算的または乗算的) を提供しますが、場合によっては、はるかに優れた事後保証も提供します。これは、与えられた入力に対する最適化問題の凸緩和を解くことによって機能するアルゴリズムの場合によく当てはまります。たとえば、最小頂点カバーの別の近似アルゴリズムがあり、線形計画緩和を解いて、緩和の値の最大 2 倍の頂点カバーを見つけます。緩和の値は最適な頂点カバーのサイズよりも大きくなることはないため、これにより別の 2 近似アルゴリズムが生成されます。これは、前の近似アルゴリズムの事前保証に似ていますが、後者の保証ははるかに優れています (実際、LP 緩和の値が最適な頂点カバーのサイズから大きく離れている場合)。

近似アルゴリズムの研究分野は、近似不可能性理論と密接に関連し、その影響を受けています。近似不可能性理論では、特定の近似比を持つ効率的なアルゴリズムが存在しないことが、（P ≠ NP予想などの広く信じられている仮説を条件として）簡約によって証明されています。計量巡回セールスマン問題の場合、最もよく知られている近似不可能性の結果は、P = NP、Karpinski、Lampis、Schmiedでない限り、近似比が123/122 ≈ 1.008196未満のアルゴリズムを除外します。^[6] Christofidesの1.5近似アルゴリズムの存在に関する知識と相まって、計量巡回セールスマンの近似可能性の閾値（存在する場合）は、123/122と1.5の間であることがわかります。

近似不可能性の結果は 1970 年代から証明されてきましたが、そのような結果はアドホックな方法で得られ、当時は体系的な理解はありませんでした。近似不可能性の結果を証明するための現代的なツールが発見されたのは、1990 年に Feige、Goldwasser、Lovász、Safra、Szegedy が独立集合の近似不可能性について発表した^[7]結果と有名なPCP 定理^[8]以来のことです。たとえば、PCP 定理は、 P ≠ NP と仮定すると、1974 年にJohnson が発表した最大 SAT、集合被覆、独立集合、および彩色に関する近似アルゴリズムはすべて最適な近似比を達成することを示しています。^[9]

すべての近似アルゴリズムが直接的な実用的応用に適しているわけではありません。一部のアルゴリズムは、非自明な線形計画法/半正定値緩和法 (楕円体アルゴリズムを呼び出す場合があります)、複雑なデータ構造、または高度なアルゴリズム手法を解く必要があり、実装上の困難な問題や、非実用的に大きな入力に対してのみ実行時間のパフォーマンス (正確なアルゴリズムよりも) が向上します。実装と実行時間の問題はさておき、近似アルゴリズムによって提供される保証自体は、実際に検討する価値があるほど強力ではない可能性があります。実際のアプリケーションで「すぐに」使用することはできませんが、このようなアルゴリズムの設計の背後にあるアイデアと洞察は、多くの場合、他の方法で実際のアルゴリズムに組み込むことができます。このように、非常に高価なアルゴリズムであっても、その研究は完全に理論的な追求ではなく、貴重な洞察をもたらす可能性があります。

他のケースでは、初期の結果が純粋に理論的な興味の対象であったとしても、時間の経過とともに理解が深まるにつれて、アルゴリズムはより実用的なものになるよう改良されることがあります。その一例は、サンジーヴ・アローラ（およびジョセフ・ミッチェル）によるユークリッドTSPの初期のPTASで、近似値 の実行時間は と非常に長かったです。[ ^10]しかし、1年以内にこれらのアイデアは、任意の定数 に対するほぼ線形時間のアルゴリズムに組み込まれました。^[11]${\displaystyle n^{O(1/\epsilon )}}$${\displaystyle 1+\epsilon }$${\displaystyle O(n\log n)}$${\displaystyle \epsilon >0}$

最適化問題が与えられた場合:

${\displaystyle \Pi :I\times S}$

ここで、は近似問題、入力の集合、および解の集合であり、コスト関数を定義できます。 ${\displaystyle \Pi}$${\displaystyle I}$${\displaystyle S}$

${\displaystyle c:S\rightarrow \mathbb {R} ^{+}}$

実行可能な解決策の集合:

${\displaystyle \forall i\in I,S(i)={s\in S:i\Pi _{s}}}$

最大化問題または最小化問題に対する 最善の解決策を見つける:${\displaystyle s^{*}}$

${\displaystyle s^{*}\in S(i)}$、${\displaystyle c(s^{*})=最小/最大\ c(S(i))}$

実行可能な解 が与えられている場合、保証されるパフォーマンスである解の品質の保証が求められます (近似係数)。 ${\displaystyle s\in S(i)}$${\displaystyle s\neq s^{*}}$

具体的には、 の場合、アルゴリズムの近似係数（または近似比）は であり、の場合、次の式が得られます。 ${\displaystyle A_{\Pi }(i)\in S_{i}}$${\displaystyle \rho (n)}$${\displaystyle \forall i\in I\ s.t.|i|=n}$

• 最小化問題の場合: 、これは、アルゴリズムによって得られた解を最適解で割った値が の比率を達成することを意味します。${\displaystyle {\frac {c(A_{\Pi }(i))}{c(s^{*}(i))}}\leq \rho (n)}$${\displaystyle \rho (n)}$
• 最大化問題の場合: 、これは最適解をアルゴリズムによって得られた解で割った値が の比率を達成することを意味します。${\displaystyle {\frac {c(s^{*}(i))}{c(A_{\Pi }(i))}}\leq \rho (n)}$${\displaystyle \rho (n)}$

アルゴリズムが近似限界で実行されるインスタンスが存在することを実証することで、近似が厳密である(厳密な近似) ことが証明され、境界の厳しさが示されます。この場合、アルゴリズムを最悪のシナリオに強制するように設計された入力インスタンスを構築するだけで十分です。

いくつかの近似アルゴリズムでは、最適結果の近似に関する特定の特性を証明することができます。たとえば、ρ近似アルゴリズム Aは、インスタンス x に対する近似解 A ( x )の値/コスト f ( x ) が最適解の値OPTの係数ρ倍より大きくならない (または、状況に応じて小さくならない) ことが証明されているアルゴリズムとして定義されます。

${\displaystyle {\begin{cases}\mathrm {OPT} \leq f(x)\leq \rho \mathrm {OPT} ,\qquad {\mbox{if }}\rho >1;\\\rho \mathrm {OPT} \leq f(x)\leq \mathrm {OPT} ,\qquad {\mbox{if }}\rho <1.\end{cases}}}$

係数ρは相対的性能保証と呼ばれる。近似アルゴリズムは、すべてのインスタンスxに対して次のこと が証明されている場合、絶対的性能保証または境界誤差 cを持つ。

${\displaystyle (\mathrm {OPT} -c)\leq f(x)\leq (\mathrm {OPT} +c).}$

同様に、インスタンスxに対するソリューションyのパフォーマンス保証R ( x,y )は次のように定義される。

${\displaystyle R(x,y)=\max \left({\frac {OPT}{f(y)}},{\frac {f(y)}{OPT}}\right),}$

ここで、f ( y ) はインスタンスxに対するソリューションyの価値/コストです。明らかに、パフォーマンス保証は 1 以上であり、y が最適ソリューションである場合にのみ 1 に等しくなります。アルゴリズムA が最大でr ( n )のパフォーマンス保証でソリューションを返すことを保証する場合、Aはr ( n ) 近似アルゴリズムと呼ばれ、近似率はr ( n ) です。同様に、 r ( n ) 近似アルゴリズムの問​​題はr ( n )近似可能である、または近似率がr ( n ) であると言われています。^{[12] [13]}

最小化問題の場合、2 つの異なる保証は同じ結果をもたらしますが、最大化問題の場合、相対的なパフォーマンス保証 ρ はパフォーマンス保証と同等です。文献では、両方の定義が一般的ですが、最大化問題の場合、ρ ≤ 1 であるのに対し r ≥ 1 であるため、どちらの定義が使用されているかは明らかです。 ${\displaystyle r=\rho ^{-1}}$

ある近似アルゴリズムAの絶対的なパフォーマンス保証は 、x が問題のインスタンスを指し、 がxに対するAのパフォーマンス保証（つまり、問題インスタンスxの ρ ）である場合、次のようになります。 ${\displaystyle \mathrm {P} _{A}}$${\displaystyle R_{A}(x)}$

${\displaystyle \mathrm {P} _{A}=\inf\{r\geq 1\mid R_{A}(x)\leq r,\forall x\}.}$

つまり、これは問題のあらゆる可能なインスタンスにわたって見られる近似比rの最大の境界です。同様に、漸近的なパフォーマンス比は次のようになります。 ${\displaystyle \mathrm {P} _{A}}$ ${\displaystyle R_{A}^{\infty }}$

${\displaystyle R_{A}^{\infty }=\inf\{r\geq 1\mid \exists n\in \mathbb {Z} ^{+},R_{A}(x)\leq r,\forall x,|x|\geq n\}.}$

つまり、これは絶対パフォーマンス比と同じですが、問題インスタンスのサイズの下限nがあります。これら 2 つの比率が使用されるのは、これら 2 つの比率の差が重要なアルゴリズムが存在するためです。

文献では、最大化（最小化）問題に対する近似比c - ϵ（最小：c + ϵ）は、アルゴリズムが任意の ϵ > 0 に対してc ∓ ϵ の近似比を持つが、 ϵ = 0 に対して比率が示されていない（または示せない）ことを意味します。 この例としては、Johan Håstadによる満足可能なMAX-3SATインスタンスに対する 7 / 8 + ϵ の最適近似不可能性（近似の非存在性）比率が挙げられます。^[14]前述のように、c = 1 の場合、問題には多項式時間近似スキームがあると言われます。

ϵ 項は、近似アルゴリズムが乗法誤差と定数誤差を導入し、サイズnのインスタンスの最小最適値がnと同様に無限大になるときに現れることがあります。この場合、近似比は、定数cとkに対してc ∓ k / OPT = c ∓ o(1) です。任意の ϵ > 0 が与えられた場合、十分に大きなN を選択して、 n ≥ Nごとに項k / OPT < ϵ となるようにすることができます。固定されたすべての ϵ に対して、サイズn < Nのインスタンスはブルートフォースで解くことができ、それによってすべての ϵ > 0 に対してc ∓ ϵの近似比 (保証付き近似アルゴリズムの存在) を示します。

• 支配分析では、計算されたソリューションのランクに基づいて保証を考慮します。
• PTAS - 近似比をパラメータとする近似アルゴリズムの一種
• パラメータ化された近似アルゴリズム- FPT時間で実行される近似アルゴリズムの一種
• APXは定数近似アルゴリズムを持つ問題のクラスである
• 近似値保存縮小
• 正確なアルゴリズム

• ヴァジラニ、ビジェイ V. (2003)。近似アルゴリズム。ベルリン：シュプリンガー。ISBN 978-3-540-65367-7。
• Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest 、Clifford Stein。アルゴリズム入門、第 2 版。MIT Press および McGraw-Hill、2001 年。ISBN 0-262-03293-7。第35章:近似アルゴリズム、pp. 1022–1056。 
• Dorit S. Hochbaum編著『NP困難問題に対する近似アルゴリズム』 PWS Publishing Company、1997年。ISBN 0-534-94968-1。第9章：近似のさまざまな概念：良い、より良い、最良、そしてそれ以上 
• ウィリアムソン、デビッド P. ;シュモイズ、デビッド B. (2011 年 4 月 26 日)、近似アルゴリズムの設計、ケンブリッジ大学出版局、ISBN 978-0521195270

• Pierluigi Crescenzi、Viggo Kann、Magnús Halldórsson、Marek Karpinski、Gerhard Woeginger、NP 最適化問題の概要。