{"id":"arxiv/2610.26967","url":"https://arxiv.org/abs/2610.26967","tags":["math.OC","cs.DM","cs.LG"],"score":0,"title":"When Weak Submodularity Meets Matroids: How Does Standard Greedy Behave?","domain":"math.OC","source":"arxiv","authors":["Qixin Zhang","Shi Fu","Shengminjie Chen","Chao Qian","Dacheng Tao"],"reviews":0,"subject":"math.OC","summary":"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_{\\mathrm{gr}}(γ,r)$ of standard forward greedy, where $r$ is the…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-18","reactions":{}}