Approximating Submodular Matroid-Constrained Partitioning

The submodular partitioning problem asks to minimize, over all partitions P of a ground set V , the sum of a given submodular function f over the parts of 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 P , and the global setting, where the only constraint is the size of the partition. We investigate a generalization that unifies these two settings: minimum submodular matroid-constrained partition. In this problem, we are additionally given a matroid over the ground set and seek to find a partition P in which there exists some basis that is separated by P . We explore the approximability of this problem and its variants for general, symmetric, and monotone submodular functions.