ラミナー被覆制約を持つ単調凹関数最小化問題

概要

論文の詳細を見る
Vを|V|=nである有限の集合とする.Vの部分集合族F⊆2^Vは,任意の集合X,Y∈Fに対して,X∩Y=〓,X⊆Y,X⊇Yのいずれかが成立するとき,ラミナー族と呼ばれる.本研究では,ラミナー族F⊆2^V,ラミナー族上の要求関数d:F→R_+,コストを表す単調凹関数F:R^V_+→R_+が与えられたとき,ラミナー被覆制約と非負制約を満たしながらコストF(x)を最小化する問題を考察する.本研究では,コスト関数Fがラミナー族Fに基づくVの分割上の単調凹関数に分離できるとき,上記の問題がO(n^2q)時間で解けることを示す.ただし,qはx∈R^v_+からF(x)を得るための計算量である.また,Fがオラクルとして与えられるときはΩ(n^2q)時間必要であり,このときには我々の提案するアルゴリズムが最適であることを示す.さらにFが固定費つきの線形関数f_v(v∈V)の和として表現できる場合に対するO(nlog^2n)時間アルゴリズムを構成する.一般の単調凹関数Fに対しては,Fがオラクルとして与えられるならば,Ω(2^<n/2>q)時間必要であり,Fが明示的に与えられる場合でもNP困難であることを示す.
2004-01-30