Our paper “Approximate Decomposable Submodular Function Minimization for Cardinality-Based Components” was just accepted for publication at NeurIPS (joint work with Austin Benson and Jon Kleinberg). The paper applies new sparsification techniques for solving a common class of decomposable submodular function minimization problems. This is motivated by applications to hypergraph clustering, but solves a more general problem.
Preprint available at https://arxiv.org/abs/2110.14859