When Weak Submodularity Meets Matroids: How Does Standard Greedy Behave?
Weakly submodular maximization finds numerous applications in machine learning, data mining and statistics. In particular, under a cardinality constraint, the standard greedy algorithm is known to attain the tight $(1-e^{-\gamma})$-approximation guarantee, where $\gamma$ denotes the submodularity ratio. However, when c...