[Submitted on 18 Oct 2026 (v1), last revised 21 Oct 2026 (this version, v2)]
Abstract: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 considering general matroid constraints, emph{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_{mathrm{gr}}(gamma,r)$ of standard forward greedy, where $r$ is the rank of matroid. Specifically, our first contribution is the following refined lower bound begin{equation*} R_{gr}(gamma,r)ge maxleft{ frac{gamma}{r}, frac{gamma^2} {B_gamma+sqrt{gamma(r-1)}}, frac{gamma^{r+1}} {2-gamma+gamma^{r+1}}, frac{gamma^2} {14left(B_gamma+sqrt{gamma(1-gamma)(r-1)}right)} right}, end{equation*} where $B_gammatriangleq2-gamma+gamma^2$. This lower bound not only strictly improves upon the previous guarantee of $0.4gamma^2/(1+sqrt{gamma r})$, but also can recover the classical $1/2$-approximation guarantee at $gamma=1$. Subsequently, a corresponding upper bound is established for $R_{mathrm{gr}}(gamma,r)$, namely, begin{equation}label{eq_upper_abstract} R_{gr}(gamma,r) leminleft{frac{1}{2},20maxleft{frac{gamma}{r}, frac{gamma^2}{B_gamma+ sqrt{gamma(1-gamma)(r-1)}}right}right}. end{equation} For every fixed $gammain(0,1)$, this equation effectively sharpens the recent $O_gamma(1/log(n-1))$ upper bound to $O_gamma(r^{-1/2})$, where $n$ is the size of ground set. Putting all these results together, we eventually can obtain [R_{gr}(gamma,r) = Thetaleft( maxleft{frac{gamma}{r}, frac{gamma^2} {1+sqrt{gamma(1-gamma)r}}right} right).]
Submission history
From: Qixin Zhang [view email]
[v1] Sun, 18 Oct 2026 16:31:33 UTC (28 KB)
[v2] Wed, 21 Oct 2026 02:00:12 UTC (28 KB)