When Weak Submodularity Meets Matroids: How Does Standard Greedy Behave?
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−γ)-approximation guarantee, where γ 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 Rgr(γ,r) of standard forward greedy, where r is the rank of matroid. Specifically, our first contribution is the following refined lower bound Rgr(γ,r)≥ max{ γ/r, γ2/(Bγ+√(γ(r−1))), (γr+1)/(2−γ+γr+1), γ2/(14(Bγ+√(γ(1−γ)(r−1)))) }, where Bγtriangleq2−γ+γ2. This lower bound not only strictly improves upon the previous guarantee of 0.4γ2/(1+√(γr)), but also can recover the classical 1/2-approximation guarantee at γ=1. Subsequently, a corresponding upper bound is established for Rgr(γ,r), namely, labelequpperabstract Rgr(γ,r) ≤min{1/2,20max{γ/r, γ2/(Bγ+ √(γ(1−γ)(r−1)))}}. For every fixed γ∈(0,1), this equation effectively sharpens the recent Oγ(1/log(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 Rgr(γ,r) = Θ( max{γ/r, γ2/(1+√(γ(1−γ)r))} ).
Related
- Poisson Exchange Beyond Submodularity: Effective Approximation Algorithms for Offline and Online Subset Selection over Matroids
- Submodularity of entropy under quantum convolution
- Tensor Product Does Not Behave Additively on Delooping Level
- Discounted Hitting Domination on Graphs with Submodularity, Complexity and Exact Algorithms
- On the Log-submodularity for zonoids: from Mixed Volume inequalities to the Hypercube
BibTeX
@misc{zhang2026when,
title = {{When Weak Submodularity Meets Matroids: How Does Standard Greedy Behave?}},
author = {Qixin Zhang and Shi Fu and Shengminjie Chen and Chao Qian and Dacheng Tao},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.26967},
eprint = {2610.26967},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.26967},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - When Weak Submodularity Meets Matroids: How Does Standard Greedy Behave?
AU - Qixin Zhang
AU - Shi Fu
AU - Shengminjie Chen
AU - Chao Qian
AU - Dacheng Tao
PY - 2026
DA - 2026/10/21
PB - arXiv
DO - 10.48550/arxiv.2610.26967
UR - https://arxiv.org/abs/2610.26967
AB - 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, \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_gr(γ,r) of standard forward greedy, where r is the rank of matroid. Specifically, our first contribution is the following refined lower bound R_gr(γ,r)≥ max{ γ/r, γ^2/(B_γ+√(γ(r−1))), (γ^r+1)/(2−γ+γ^r+1), γ^2/(14(B_γ+√(γ(1−γ)(r−1)))) }, where B_γtriangleq2−γ+γ^2. This lower bound not only strictly improves upon the previous guarantee of 0.4γ^2/(1+√(γ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, labeleq_upper_abstract R_gr(γ,r) ≤min{1/2,20max{γ/r, γ^2/(B_γ+ √(γ(1−γ)(r−1)))}}. For every fixed γ∈(0,1), this equation effectively sharpens the recent O_γ(1/log(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_gr(γ,r) = Θ( max{γ/r, γ^2/(1+√(γ(1−γ)r))} ).
ER -