FIT2015第14回情報科学技術フォーラム 開催日:2015年9月15日(火)~17日(木) 会場:愛媛大学城北キャンパス
抄録
RA-001
正モジュラ関数の最適化
石井利昌(北大)・牧野和久(京大)
正モジュラ関数は,無向グラフのカット関数など様々な組合せ最適化問題に関連して現れる重要な離散構造である.正モジュラ関数の最小化問題は,エグレス(Egres)未解決問題に示された重要な未解決問題であるが,本論文では指数時間必要である,より正確には,Ω(2n/7.54) 回のオラクル呼び出しが必要であることを示す.ただし,nは台集合のサイズである.また,値域がD={0,1,…, d} (d は正整数)のとき,Ω(2d/15.08)回のオラクル呼び出しが必要である一方,O(ndTf+n2d+1) 時間で計算可能であることを示す.ただし,Tfは,X⊆Vに対して関数値f(X)の計算に要する時間を表す. さらに,正モジュラ関数の最大化問題に対して,Ω(2n-1) 回のオラクル呼び出しが必要であり,値域がDのときの計算時間がΘ(nd-1Tf)であることを示す.