Weakly Submodular Maximization Beyond Cardinality Constraints: Does Randomization Help Greedy?

Lin Chen, Moran Feldman, Amin Karbasi

Submodular functions are a broad class of set functions, which naturally arise in diverse areas. Many algorithms have been suggested for the maximization of these functions. Unfort…