【研究分野】情報学基礎

【研究領域課題番号】23300002 (KAKENデータベースで見る）

【研究キーワード】

離散最適化 / 劣モジュラ関数 / 近似アルゴリズム / NP困難 / ネットワーク / 離散凸性 / 巡回セールスマン問題 / 組合せ剛性理論

【研究成果の概要】

劣モジュラ関数は，効率的に解くことのできる離散最適化問題に共通の構造して知られている．一方，実務上重要な多くの離散最適化問題はNP困難であり，現実的な時間内で近似解を得る近似アルゴリズムの設計が研究されてきた．本研究では，このような離散最適化の二つの大きな流れを融合して，汎用性の高い近似アルゴリズムを設計する手法を研究した．特に，劣モジュラ関数の一般化に当たるk劣モジュラ関数の最大化問題に対して，近似比1/2の近似アルゴリズムを設計した．さらに，単調k劣モジュラ関数に対しては，近似比がk/2(k-1)となる多項式時間アルゴリズムを開発した．

【研究種目】基盤研究(B)

【研究期間】2011-04-01 - 2016-03-31

【配分額】12,610千円 (直接経費: 9,700千円、間接経費: 2,910千円)