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

Submodular functions are a broad class of set functions, which naturally\narise in diverse areas. Many algorithms have been suggested for the\nmaximization of these functions. Unfortunately, once the function deviates from\nsubmodularity, the known algorithms may perform arbitrarily poorly. Amending\nthis issue, by obtaining approximation results for set functions generalizing\nsubmodular functions, has been the focus of recent works.\n One such class, known as weakly submodular functions, has received a lot of\nattention. A key result proved by Das and Kempe (2011) showed that the\napproximation ratio of the greedy algorithm for weakly submodular maximization\nsubject to a cardinality constraint degrades smoothly with the distance from\nsubmodularity. However, no results have been obtained for maximization subject\nto constraints beyond cardinality. In particular, it is not known whether the\ngreedy algorithm achieves any non-trivial approximation ratio for such\nconstraints.\n In this paper, we prove that a randomized version of the greedy algorithm\n(previously used by Buchbinder et al. (2014) for a different problem) achieves\nan approximation ratio of $(1 + 1/\\gamma)^{-2}$ for the maximization of a\nweakly submodular function subject to a general matroid constraint, where\n$\\gamma$ is a parameter measuring the distance of the function from\nsubmodularity. Moreover, we also experimentally compare the performance of this\nversion of the greedy algorithm on real world problems against natural\nbenchmarks, and show that the algorithm we study performs well also in\npractice. To the best of our knowledge, this is the first algorithm with a\nnon-trivial approximation guarantee for maximizing a weakly submodular function\nsubject to a constraint other than the simple cardinality constraint. In\nparticular, it is the first algorithm with such a guarantee for the important\nand broad class of matroid constraints.\n