On Maximizing a Weakly Submodular Function over a Matroid Constraint via the Greedy Algorithm

Justin Ward, Moran Feldman

We consider the problem of approximately maximizing a weakly submodular function using the standard greedy algorithm, which is known to give tight approximation results for such fu…