International Joint Conference On Theoretical Computer Science – Frontier of Algorithmic Wisdom

August 15-19, 2022, City University of Hong Kong, Hong Kong

 

Invited Speakers

Young Faculty Forum in TCS


A polynomial time algorithm for submodular 4-partition

Chao Xu

University of Electronic Science and Technology of China

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

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.