When Weak Submodularity Meets Matroids: How Does Standard Greedy Behave?

Qixin Zhang, Shi Fu, Shengminjie Chen +2

Weakly submodular maximization finds numerous applications in machine learning, data mining and statistics. In particular, under a cardinality constraint, the standard greedy algor…