Approximating Minimum k-partitions in Submodular Systems
Hiroshi Nagamochi · 2007
In this paper, we consider the problem of computing a minimum k-partition of a finite set V with a set function f : 2Vrarr Ropf, where the cost of a k-partition {V1, V2,..., Vk} is defined by Sigma1lesileskf(Vi). 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|3)-oracle time. This improves the previous best time bound by a factor of k = O(|V|)