Chao Xu: A polynomial time algorithm for submodular 4-partition
- Speaker
- Chao Xu
- Affiliation
- University of Electronic Science and Technology of China
- Date
- Time
- – Asia/Shanghai
- Venue
- Online
Abstract
We study the submodular $k$-partition problem. That is, 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 the 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 fixed $k \leq 3$. We construct the first polynomial-time algorithm for the minimum $4$-partition problem.
This is joint work with Tsuyoshi Hirayama, Yuhao Liu, Kazuhisa Makino and Ke Shi.
Speaker Bio
Chao Xu is currently an Assistant Professor at Algorithms and Logic Group in UESTC. He obtained a Ph.D. degree of Computer Science at UIUC in May 2018. He works in the area of combinatorial optimization, algorithms and computational geometry.
Livestream
Online:
https://live.bilibili.com/22051279
https://www.youtube.com/channel/UCkbCc-9vJXb4RZQA0wOPoTw/live