劣モジュラシステム分割問題に対するアルゴリズム

摘要

有限集合Vと，劣モジュラ性を持つV上の集合関数f:2~V→Rの組を劣モジュラシステムと呼ぶ．劣モジュラシステムのた分割問題とは，∑f（V_i） (i from 1 to k)を最小化するVのた分割｛V_1，…，V_k}を求める問題である．本報告では，k=3の場合に対する多項式時間厳密アルゴリズムを与える．k=4の場合に対する多項式時間1.5近似アルゴリズム，k=5の場合に対する多項式時間2近似アルゴリズムについても触れる．また，劣モジュラシステムのk分割問題がハイパーグラフのk分割問題を含むことを示し，我々の近似アルゴリズムがハイパーグラフに対してはよりよい近似精度を達成することについても述べる．