In this paper, we consider the problem
of computing a minimum k-partition
of a finite set V with a set function
f from 2^V to the set of reals, where the cost of a k-partition {V_1,V_2,\ldots,V_k} is defined by f(V_1)+f(V_2)+...+f(V_k).
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\in [1,|V|] can be obtained in O(|V|^3)-oracle time.
This improves the previous best time bound by a factor of k=O(|V|).