A polynomial time algorithm for finding a minimum 4-partition of a submodular function

• 成果类型: Article
• 署名作者: Hirayama, Tsuyoshi; Liu, Yuhao; Makino, Kazuhisa; Shi, Ke; Xu, Chao
• 署名单位: University of Electronic Science & Technology of China; Kyoto University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-023-02029-0
• 发表日期: 2024
• 页码: 717-732
• 关键词: greedy splitting algorithms; cuts; 3-way

摘要

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 : 2(V) -> R, computing a k-partition {V-1, ... , V-k} of V with minimum Sigma k(i=1) f(V-i). 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 k <= 3. In this paper, we construct the first polynomial-time algorithm for the minimum 4-partition problem.