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

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

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.