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

摘要

A submodular system (V, f) is a pair of a finite set V and a submodular function f : 2~V → R. The k-partition problem for submodular systems is to find a partition {V_1,..., V_k} of V into k non-empty subsets minimizing Σ_(i=1)~k f (V_i). In this report, we present a polynomial-time exact algorithm for the case of k = 3. We also discuss a polynomial-time 1.5-approximation algorithm for the case of k = 4 and a polynomial-time 2-approximation algorithm for the case of k = 5. In addition, we mention that the k-partition problem for submodular systems contains the k-partition problem for hypergraphs, and that our approximation algoriothms achieve better approximation retios for hypergraphs.%有限集合Vと，劣モジュラ性を持つV上の集合関数f：2~V→Rの組を劣モジュラシステムと呼ぶ.劣モジュラシステムのk分割問題とは，∑_(i=1)~k f（V_i）を最小化するVのk分割{V_1，…，V_k}を求める問題である.本報告では，k＝3の場合に対する多項式時間厳密アルゴリズムを与える.k＝4の場合に対する多項式時間1.5近似アルゴリズム，k＝5の場合に対する多項式時間2近似アルゴリズムについても触れる.また，劣モジュラシステムのk分割問題がハイパーグラフのk分割問題を含むことを示し，我々の近似アルゴリズムがハイパーグラフに対してはよりよい近似精度を達成することについても述べる.