Submodular Maximization Beyond Non-negativity: Guarantees, Fast Algorithms, and Applications

Christopher Harshaw, Moran Feldman, Justin Ward +1

It is generally believed that submodular functions -- and the more general class of $\gamma$-weakly submodular functions -- may only be optimized under the non-negativity assumption $f(…