Sparsify Submodular Functions under Cardinality Constraints (opens in new tab)

Submodular sparsification generalizes the classical sparsification problems of graphs and matrices to summations of submodular functions. Given the summation $F(S):=f_1(S)+\cdots+f_m(S)$ of $m$ submodular functions $f_1,\ldots,f_m:\{0,1\}^n \to \mathbb{R}_{\ge 0}$. An size-$s$ sparsification of $F$ is a weight vector $w \in \mathbb{R}^m_{\ge 0}$ such that $w_1 f_1(S) + \cdots w_m f_m(S) \approx F(S)$ for every subset $S \subset [n]$. Motivated b...