Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2007-007 (February 06, 2007)

Approximating Minimum k-partitions in Submodular Systems
by Hiroshi Nagamochi

pdf File

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|).