General Events - Department of Mathematics

View Full Calendar

Combinatorics Colloquium: On Submodular k-Partitioning and Hypergraph k-Cut

Event Type
Seminar/Symposium
Sponsor
n/a
Location
245 Altgeld Hall
Date
Dec 2, 2021   4:00 pm  
Speaker
Chandra Checkuri, UIUC Computer Science Dept.
Contact
Jozsef Balogh
E-Mail
jobal@illinois.edu
Views
29

Submodular $k$-Partition is the following problem: given a submodular set function $f:2^V \rightarrow \mathbb{R}$ and an integer $k$, find a partition of $V$ into $k$ non-empty parts $V_1,V_2,\ldots,V_k$ to minimize $\sum_{i=1}^k f(V_i)$.  Several interesting problems such as Graph $k$-Cut, Hypergraph $k$-Cut and Hypergraph $k$-Partition are special cases.  Submodular $k$-Partition admits a polynomial-time algorithm for $k=2,3$ and when $f$ is symmetric also for $k=4$.  The complexity is open for $k=4$ and when $f$ is symmetric for $k=5$.

In recent work, motivated by this problem, we examined the complexity of Hypergraph $k$-Cut which only recently admitted a randomized polynomial-time algorithm. We obtained a deterministic polynomial-time algorithm for Hypergraph $k$-Cut as well as new insights in to Graph $k$-Cut. The ideas also led to a polynomial-time algorithm for Min-Max Symmetric Submodular $k$-Partition for any fixed $k$.

The talk will discuss these results with the goal of highlighting the open problem of resolving the complexity of Submodular $k$-Partition.

Based on joint work with Karthik Chandrasekharan

link for robots only