2009年4月10日
劣モジュラシステム分割問題に対するアルゴリズム
電子情報通信学会技術研究報告. COMP, コンピュテーション
- ,
- ,
- 巻
- 109
- 号
- 9
- 開始ページ
- 7
- 終了ページ
- 14
- 記述言語
- 日本語
- 掲載種別
- 出版者・発行元
- 一般社団法人電子情報通信学会
有限集合Vと,劣モジュラ性を持つV上の集合関数f:2^V→Rの組を劣モジュラシステムと呼ぶ.劣モジュラシステムのk分割問題とは,Σ^k_<i=1>f(V_i)を最小化するVのk分割{V_1,…,V_k}を求める問題である.本報告では,k=3の場合に対する多項式時間厳密アルゴリズムを与える.k=4の場合に対する多項式時間1.5近似アルゴリズム,k=5の場合に対する多項式時間2近似アルゴリズムについても触れる.また,劣モジュラシステムのk分割問題がハイパーグラフのk分割問題を含むことを示し,我々の近似アルゴリズムがハイパーグラフに対してはよりよい近似精度を達成することについても述べる.
- リンク情報
-
- CiNii Articles
- http://ci.nii.ac.jp/naid/110007227314
- CiNii Books
- http://ci.nii.ac.jp/ncid/AN10013152
- URL
- http://id.ndl.go.jp/bib/10219936
- ID情報
-
- ISSN : 0913-5685
- CiNii Articles ID : 110007227314
- CiNii Books ID : AN10013152