近似アルゴリズム

コンピュータサイエンスとオペレーションズリサーチにおいて、近似アルゴリズムは、最適解と最適解との距離について証明可能な保証付きで、最適化問題（特にNP困難問題）の近似解を見つける効率的なアルゴリズムです。 ^{[ 1 ]}近似アルゴリズムは、広く信じられているP≠NP予想の結果として、理論計算機科学の分野で自然に発生しました。この予想の下では、多くのクラスの最適化問題を多項式時間で厳密に解くことはできません。したがって、近似アルゴリズムの分野では、そのような問題の最適解を多項式時間でどれだけ正確に近似できるかを理解しようとします。圧倒的多数の場合、このようなアルゴリズムの保証は、近似比または近似係数として表現される乗法的なものです。つまり、最適解は常に、返された解の（あらかじめ決められた）乗法係数の範囲内にあることが保証されます。しかし、返された解の品質について加法的な保証を提供する近似アルゴリズムも多数存在します。乗法的な保証を持つ近似アルゴリズムの例として、巡回セールスマン問題に対するクリストフィデス・セルジュコフアルゴリズムが挙げられます。このアルゴリズムは、最短の巡回セールスマン巡回の長さの 3/2 倍以下の長さの巡回セールスマン巡回を提供します。加法的な保証を提供する近似アルゴリズムの古典的な例として、ヴィジングの定理の構成的証明が挙げられます。これは、無向グラフの辺を最大で 1/2 の長さで彩色する方法を示しています。${\displaystyle \Delta +1}$色、${\displaystyle \Delta }$は任意のノードの最大次数です。最大次数ノードに接続するすべてのエッジは異なる色を持つ必要があるため、定理の構成的証明は、必要最小限の色よりも最大で 1 つの追加色を使用する多項式時間アルゴリズムを提供します。両方を提供する近似アルゴリズムの注目すべき例は、無関係な並列マシンでのスケジューリングのためのLenstra、Shmoys、およびTardos ^{[ 2 ]}による古典的な近似アルゴリズムです。

近似アルゴリズムの設計と分析には、最悪の場合における返される解の品質を証明する数学的証明が不可欠です。 ^{[ 1 ]}これは、一部の入力に対しては比較的良い解を見つけるものの、成功または失敗する可能性があるかどうかについて最初から明確な兆候を提供しない、焼きなまし法や遺伝的アルゴリズムなどのヒューリスティックとは区別されます。

理論計算機科学では、特定の有名な最適化問題をどの程度近似できるかという限界をよりよく理解することに広く関心が寄せられています。たとえば、計算機科学における長年の未解決問題の 1 つは、Agrawal らによる Steiner Forest 問題の 2 近似を上回るアルゴリズムが存在するかどうかを判断することです。^{[ 3 ]}近似可能性の観点から難しい最適化問題を理解したいという願望は、驚くべき数学的関連性の発見と、難しい最適化問題のアルゴリズムを設計するための広く適用可能な手法によって動機付けられています。前者のよく知られた例の 1 つは、最大カットのGoemans–Williamson アルゴリズムで、これは、平方和階層の第 1 レベルから得られる半正定値計画を使用してグラフ理論問題を解きます。^{[ 4 ]}

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

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

現在では、近似アルゴリズムを設計するための確立された手法がいくつか存在する。それらには以下のようなものがある。

1. 貪欲アルゴリズム
2. ローカル検索
3. 列挙法と動的計画法（パラメータ付き近似にもよく用いられる）
4. 数理計画法。これは、線形計画法、半正定値計画法など、適切な数理計画法（典型的には凸計画法）を用いて対象問題をモデル化し、問題の緩和解を得るものです。その後、これらの定式化に対してさらにアルゴリズム的手法が適用されます。
   • 丸め処理に基づく方法。これは、対象となる定式化を解いて適切な分数解を求め、それを整数解に変換するものです。一般的な丸め処理手法には、単純な閾値丸め、ランダム丸め、反復丸めなどがあります。
   • 双対適合法。これは、意図された組み合わせベースのアルゴリズム（通常は貪欲法）を、検討対象の定式化の双対プログラムの実行可能解を計算するプロセスとして解釈するものです。
   • 原初双対法。
5. 問題を何らかの指標に埋め込み、その指標上で問題を解決する。これは指標埋め込みとも呼ばれる。
6. 無作為抽出、および上記の方法と併用した一般的な無作為性の利用。

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

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

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

すべての近似アルゴリズムが直接的な実用化に適しているわけではありません。中には、非自明な線形計画問題や半正定値緩和問題（それ自体が楕円体アルゴリズムを呼び出す場合もある）、複雑なデータ構造、あるいは高度なアルゴリズム技術を必要とするものもあり、実装上の問題が生じたり、実行時間が（厳密アルゴリズムと比較して）改善されるのは、実用上不可能なほど大きな入力の場合に限られたりします。実装や実行時間の問題とは別に、近似アルゴリズムが提供する保証自体が、実用化を検討するに値するほど強力ではない場合もあります。実用化においてそのまま使用できないにもかかわらず、こうしたアルゴリズムの設計の背後にある考え方や洞察は、他の方法で実用的なアルゴリズムに組み込むことができる場合が多くあります。このように、非常にコストのかかるアルゴリズムの研究でさえ、完全に理論的な探求にとどまらず、貴重な洞察をもたらす可能性があるのです。

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

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

${\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^{*})=min/max\ c(S(i))}$

実行可能な解が与えられた場合${\displaystyle s\in S(i)}$、 と$s\neq s^{*}}$そのため、我々は解の品質の保証、すなわち保証されるべき性能（近似係数）を望みます。

具体的には、${\displaystyle A_{\Pi }(i)\in S_{i}}$このアルゴリズムの近似係数（または近似比）は${\displaystyle \rho (n)}$もし${\displaystyle \forall i\in I\ st|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{件}}}$

係数ρは相対性能保証と呼ばれます。近似アルゴリズムは、すべてのインスタンス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 つの異なる保証は同じ結果をもたらし、最大化問題の場合、ρ の相対的パフォーマンス保証は、パフォーマンス保証と同等です。${\displaystyle r=\rho ^{-1}}$文献では両方の定義が一般的ですが、最大化問題では ρ ≤ 1 かつ r ≥ 1 であるため、どちらの定義が使用されているかは明らかです。

絶対的な性能保証${\displaystyle \mathrm {P} _{A}}$ある近似アルゴリズムAの、ここでx は問題のインスタンスを指し、${\displaystyle R_{A}(x)}$xに対するAの性能保証(すなわち、問題インスタンスxに対する ρ ) は次のとおりです。

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

つまり${\displaystyle \mathrm {P} _{A}}$これは、問題のあらゆる可能なインスタンスにおいて見られる近似比rの最大の上限です。同様に、漸近性能比${\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種類の比率が使用されるのは、両者の差が顕著なアルゴリズムが存在するためです。

文献では、c - ϵ (min: 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に対して項k / OPT < εとなるように十分大きなN を選択できます。固定された ε に対して、サイズ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章：近似アルゴリズム、 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 最適化問題の概要。