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 , computing a k-partition 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 fixed . In this paper, we construct the first polynomial-time algorithm for the minimum 4-partition problem.