A Polynomial Time Algorithm for Finding a Minimum 4-Partition of a Submodular Function
Tsuyoshi Hirayama, Yuhao Liu, Kazuhisa Makino, Ke Shi, Chao Xu · Society for Industrial and Applied Mathematics eBooks · 2023
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.