Fast Non-Monotone Submodular Maximisation Subject to a Matroid Constraint

Pau Segui-Gasco, Hyo-Sang Shin

In this work we present the first practical $\left(\frac{1}{e}-\epsilon \right)$-approximation algorithm to maximise a general non-negative submodular function subject to a matroid constra…