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

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.