Nearly Optimal Submodular Sparsification, with and without Cardinality Constraints

Zhengting Bao, Dongrun Cai, Xue Chen +2

We study the sparsification of decomposable submodular functions: given a sum $F(S)={\sum }_{i=1}^m{f}_i(S)$ of $m$ nonnegative submodular functions on an $n$-element ground set $[n]…