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

Abstract

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 functions under a cardinality constraint. We show that this is not the case for general matroid constraints. For any $\gamma <1$, we give a family of $\gamma$-weakly submodular functions and a simple partition matroid constraint and show that the standard greedy algorithm provides no constant approximation for the resulting constrained maximization problem.