Speaker:

Ke Shi (University of Electronic Science and Technology of China)

Time:

• 16:20-17:20 (Time in Beijing)
• October 21, 2022 (Friday)

Venue:

518, Research Building 4

Abstract:

We study the minimum k-partition problem of submodular functions, i.e., given a finite set V and a submodular function f:2^V\to \R, computing a k-partition \{ V_1, \ldots, V_k \} of V with minimum \sum_{i=1}^k 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 k \leq 3.
We construct the first polynomial-time algorithm for the minimum 4-partition problem.