Algorithms and Logic Group

Chao Xu: A polynomial time algorithm for submodular 4-partition

Speaker:

Chao Xu (University of Electronic Science and Technology of China)

Time:

  • 17:00-17:30 (Time in Beijing)
  • August 16, 2022 (Tuesday)

Venue:

Online:

https://live.bilibili.com/22051279

https://www.youtube.com/channel/UCkbCc-9vJXb4RZQA0wOPoTw/live

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.

,