変移する要素間の関係を条件とする組合せ最適化モデル

本研究では,入力要素の値が時間とともに連続的に変移する環境において,要素間の関係が時々刻々と変化するような様々な問題を扱い,数理最適化モデルとして定式化する統一的な手法の検討と,精度の高い近似解及び高速性能を保証するアルゴリズムの開発を目的とする.今年度は,次のような組合せ最適化モデルの形式化および計算量に関する検討を行った.1.WWWは,ウェブページとハイパーリンクから構成されており,ユーザーはハイパーリンクをクリックして次々にウェブページを表示しながらインターネット上を巡回して,目的のページに辿り着く.希望するウェブページへのアクセスを改善するための自然な解決方法は,ブックマークと呼ばれるショートカットリンクを追加することによりリンク構造を変更していくことである.本問題はブックマーク最適化問題として知られているが,近似可能性および近似不可能性に関する結果は示されていなかった.本研究課題においては,近似比(1-1/e)を持つ多項式時間アルゴリズムが存在すること,入力サイズをNとするとき,NP⊆DTIME(N^o(loglogN))でないという仮定の下で,(1-1/e)よりも良い近似比を持つ多項式時間アルゴリズムが存在しないこと,δをある小さな正定数とするとき,より弱いP=NPでないという仮定の下で,(1-δ)よりも良い近似比を持つ多項式時間アルゴリズムは存在しないということを示した.2.仕事の要求列とその要求列の一部を一時的に保存できるソーティングバッファが与えられた時,要求列の一部を置換することにより仕事効率を上げることを目的としたソーティングバッファ最適化問題について,オンラインモデルに対するFIFOアルゴリズムの競合比の上限と,オフラインモデルの計算複雑さを示した.

本研究では,入力要素の値が時間とともに連続的に変移する環境において,要素間の関係が時々刻々と変化するような様々な問題を扱い,数理最適化モデルとして定式化する統一的な手法の検討と,精度の高い近似解及び高速性能を保証するアルゴリズムの開発を目的とする.今年度は,次のような組合せ最適化モデルの形式化および計算量に関する検討を行った.1.WWWは,ウェブページとハイパーリンクから構成されており,ユーザーはハイパーリンクをクリックして次々にウェブページを表示しながらインターネット上を巡回して,目的のページに辿り着く.希望するウェブページへのアクセスを改善するための自然な解決方法は,ブックマークと呼ばれるショートカットリンクを追加することによりリンク構造を変更していくことである.本問題はブックマーク最適化問題として知られているが,近似可能性および近似不可能性に関する結果は示されていなかった.本研究課題においては,近似比(1-1/e)を持つ多項式時間アルゴリズムが存在すること,入力サイズをNとするとき,NP⊆DTIME(N^o(loglogN))でないという仮定の下で,(1-1/e)よりも良い近似比を持つ多項式時間アルゴリズムが存在しないこと,δをある小さな正定数とするとき,より弱いP=NPでないという仮定の下で,(1-δ)よりも良い近似比を持つ多項式時間アルゴリズムは存在しないということを示した.2.仕事の要求列とその要求列の一部を一時的に保存できるソーティングバッファが与えられた時,要求列の一部を置換することにより仕事効率を上げることを目的としたソーティングバッファ最適化問題について,オンラインモデルに対するFIFOアルゴリズムの競合比の上限と,オフラインモデルの計算複雑さを示した.