Domination analysis for minimum multiprocessor scheduling

Gregory Gutin, Tommy Jensen, and Anders Yeo
Discrete Applied Mathematics
Volume 154, Issue 18 , 1 December 2006, Pages 2613-2619
http://dx.doi.org/10.1016/j.dam.2006.02.010

Domination analysis (支配解析とでも訳すのだろうか) に関する論文。
Glover and Punnen (1997) が提唱しているdomination analysisをGutinらは精力的に研究しつづけている。
精力的なのは彼らだけに思えるが、それでもちゃんとやりつづけている根気はすごい。

実行可能集合が有限な最適化問題 (典型的には組合せ最適化問題) Pに対する (厳密に解くとは限らない) アルゴリズムAを考える。
問題PのインスタンスIに対するAの出力値をA(I)と書くことにして、Iの実行可能解の中で目的関数値がA(I)以下のものの割合を考える。
この割合がAのIに対する支配比 (domination ratio) と呼ばれるもので、これが大きければ大きいほど (1に近ければ近いほど) 厳密アルゴリズムに近い、ということになる。
これはアルゴリズムの出力値と最適値を比較する「近似比」という概念に比べて頑健であることが分かる。
例えば、目的関数を2乗すると近似比は変わってしまうが支配比は変わらない。

今、サイズsのインスタンスI全体における支配比のsupremumをdomr(A,s)と書くことにする。
このsを無限大に持っていったときのdomr(A,s)の極限が1となるような多項式時間アルゴリズムAのことをADROアルゴリズムと呼ぶことにする。
ADROはasymptotic domination ratio oneの略。
Alon, Gutin and Krivelevich (2004) は分割問題に対するADROアルゴリズムを提案した。
この問題は2機械スケジューリングに対応するが、本論文ではそれを他機械スケジューリングに拡張して、ADROアルゴリズムを導いている。

考えている問題はいわゆる他機械スケジューリングで、p個の機械はすべて同一で並列処理が可能であり、最終完了時刻 (makespan) を最小化するものである。
アルゴリズムは次のようなものである。インスタンスのサイズはsで、ジョブの数はnであるとする。
まずsがpのn乗以上の場合、n個のジョブをp個の機械へ割り当てる場合の数が高々オーダーpのn乗なので、sに関する多項式時間で最適に解くことができる。
よって、sがpのn乗よりも小さい場合を考える。
この場合、まずn個のジョブの中から処理時間の大きいものを順にr個とってくる。ただしrは(log n/log p)の切り上げ。
そして、これらr個のジョブに関して最適に問題を解く。
次に残されたジョブについては、また処理時間の大きいものから順にp個の機械中負荷がもっとも小さいところへ貪欲に割り当てていく。
これがアルゴリズムであり、論文ではADROアルゴリズムであることが証明されている。