Approximating Minimum k-partitions in Submodular Systems

In this paper, we consider the problem of computing a minimum k-partition of a finite set V with a set function f : 2^V rarr Ropf, where the cost of a k-partition {V₁, V₂ ,..., V_k} is defined by Sigma_1lesileskf(V_i). This problem contains the problem of partitioning a vertex set of an edge-weighted hypergraph into k components by removing the least cost of hyperedges. We show that, for a symmetric and submodular set function f, 2(1 - 1/k)-approximate solutions for all k isin [1, |V|] can be obtained in O(|V|³)-oracle time. This improves the previous best time bound by a factor of k = O(|V|)