Domination analysis とは

近似アルゴリズムの支配分析は、1997年にGloverとPunnenによって導入されたその性能を評価する方法です。計算された解の数値品質と最適解の数値品質を比較する古典的近似比分析とは異なり、支配分析は、すべての可能な解のソートされた順序で計算された解の順位。この分析スタイルでは、アルゴリズムの出力が最良である問題に対するK個の異なる解のサブセットが存在する場合、アルゴリズムは支配数または支配数Kを有すると言われる。支配分析は、与えられた解よりも優れていない解空間の割合である支配率を使用して表すこともできます。この数値は常に区間[0,1]内にあり、数値が大きいほど解が良いことを示します。支配分析は、可能な解決策の総数が分かっており、厳密な解決が難しい問題に最も一般的に適用されます。
例えば、トラベリングセールスマンの問題には、(n-1)! n都市の問題インスタンスに対する可能な解法。 (n-1)!に近い支配数を持つアルゴリズム、または同等に支配比を1に近づけるアルゴリズムを示すことができれば、支配数の低いアルゴリズムよりも好ましいと考えることができます。
トラベリングセールスマンの問題のように、問題の解空間の無作為標本を効率的に見つけることができる場合は、無作為アルゴリズムが高い確率で高い優位な解を見つけることは簡単です。それらの中から最良のソリューションを選択してください。 (例えば、OrlinおよびSharmaを参照のこと)。
ここに記載されている支配数は、グラフの支配数と混同してはなりません。グラフの支配的な集合の頂点の数を指します。
近年、ヒューリスティックの性能を評価するために支配分析が適用されている記事が増えている。この種の分析は、古典的な近似比分析の伝統と競合すると見なすことができる。 2つの尺度は相補的と見なすこともできる。