A Polynomial Time Algorithm for Finding a Minimum 4-Partition of a Submodular Function

In this paper, we study the minimum k-partition problem of submodular functions, i.e., given a finite set V and a submodular function f: 2V → ℝ, computing a k-partition V1,…, Vk of V with minimum . The problem is a natural generalization of the minimum k-cut problem in graphs and hypergraphs. It is known that the problem is NP-hard for general k, and solvable in polynomial time for k ≤ 3. In this paper, we construct the first polynomial-time algorithm for the minimum 4-partition problem. * Authors are ordered alphabetically.