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-γ) -approximation guarantee, where γ denotes the submodularity ratio. However, when considering general matroid constraints, how well standard greedy can perform has remained a longstanding open question. In this paper, we resolve this question by studying the worst-case approximation guarantee R gr(γ,r) of standard forward greedy, where r is the rank of matroid. Specifically, our first contribution is the following refined lower bound R(γ,r) γ r, B γ+ sqrt γ(r-1), 2-γ+γ r+1, 14 (B γ+ sqrt γ(1-γ)(r-1)), where B γ 2-γ+γ squared. This lower bound not only strictly improves upon the previous guarantee of 0.4γ 2/(1+ sqrt γr), but also can recover the classical 1/2-approximation guarantee at γ=1. Subsequently, a corresponding upper bound is established for R gr(γ,r), namely, R(γ,r) 1 over 2,20 γ r, γ squared over B γ+ sqrt γ(1-γ)(r-1). For every fixed γ in(0,1), this Eq. effectively sharpens the recent O γ(1/ (n-1)) upper bound to O γ(r-1/2), where n is the size of ground set. Putting all these results together, we eventually can obtain [R(γ,r) = Θ! (γ r, 1+ sqrt γ(1-γ)r).]