Department of Mathematics Calendar

Back to Listing

The Department of Mathematics Calendar has moved to Webtools. Anyone may submit an event by clicking the "+" button (upper right). Note: the Sponsor field is required. Just type "n/a"

All events will be reviewed before acceptance. Please email Shelby Koehne if you have any questions about submitting an event.

Note: you may search past and future events by clicking on the magnifying glass icon on the main Calendar page.

For an archive of past events:

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

Event Type
245 Altgeld Hall
Dec 2, 2021   4:00 pm  
Chandra Checkuri, UIUC Computer Science Dept.
Jozsef Balogh

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