離散最適化基礎論 (第14回 (最終回)) 多項式時間近似スキーム 2025年1月28日

電気通信大学大学院情報理工学研究科情報・ネットワーク工学専攻
岡本 吉央
dopal.cs.uec.ac...
離散最適化基礎論 (ジョブ・スケジューリングのアルゴリズム)
40:22 授業の中で説明をとばしてしまったところを補足します．
18ページ目の「J(short)に対する近似値 ≦ J(short)に対する最適値 + 2εT/5」という不等式が成り立つ理由を説明します (証明します)．
短いジョブの処理時間の総和をSとします．SをεT/5で割って，その商をq，余りをrとします (つまり，S = q(εT/5) + r)．アルゴリズムでは，処理時間が ε
T/5であるq個のジョブをm個の機械に最適に割り当てて，その後で，q個のジョブに対応させて，元の短いジョブを割り当てました．
まず，J(short)に対する最適値の下界を与えます．処理時間の総和がSであるジョブをm個の機械に割り当てるので，J(short)に対する最適値はS/m以上です．このとき，S/m = (qεT/5 + r)/m ≧ (q εT/5)/m が成り立つことに注意します．
アルゴリズムでは，まずq個の仮想的なジョブ (処理時間は ε
T/5) をm個の機械に最適に割り当てるので，その時点の完了時刻は [q/m] εT/5 です ([.] は小数点以下切り上げを表します)．そして，その後で短いジョブに置き換えますが，その置き換えによって，完了時刻は高々εT/5だけ増えます．したがって，J(short)に対する近似値は ([q/m]+1)εT/5 以下です．さらにこれは (q/m + 2)εT/5 以下です．
一方で，J(short)に対する最適値は S/m 以上ですが，これは (qεT/5)/m = (q/m)εT/5 以上だと上で確認しました．そのため，J(short)に対する近似値は，最適値 + 2εT/5以下であることになります．これで説明 (証明) を終わります．

[@okamoto7yoshio]

40:22 の辺りで忘れてしまったといった不等式の証明は説明欄 (概要欄) に書きましたので，そちらをご参照ください．