Description
The submodular partitioning problem asks to minimize, over all partitions $\mathcal{P}$ of a ground set $V$, the sum of a given submodular function $f$ over the parts of $\mathcal{P}$. The problem has seen considerable work in approximability, as it encompasses multiterminal cuts on graphs, $k$-cuts on hypergraphs, and elementary linear algebra problems such as matrix multiway partitioning. This research has been divided between the fixed terminal setting, where we are given a set of terminals that must be separated by $\mathcal{P}$, and the global setting, where the only constraint is the size of the partition. We investigate a generalization that unifies these two settings: submodular matroid-constrained partition. In this problem,
we are additionally given a matroid over the ground set and seek to find a partition $\mathcal{P}$ in which \emph{there exists} some basis that is separated by $\mathcal{P}$.
In this talk, I will discuss some results for certain classes of submodular functions, and share ongoing work involving the principal lattice of partitions of a submodular function, and methods to compute the partition minimizing a certain intersecting submodular function.