{"id":"arxiv/2609.24569","url":"https://arxiv.org/abs/2609.24569","tags":["cs.DS","cs.LG","math.OC"],"score":0,"title":"Poisson Exchange Beyond Submodularity: Effective Approximation Algorithms for Offline and Online Subset Selection over Matroids","domain":"cs.DS","source":"arxiv","authors":["Shi Fu","Youming Qiao","Dacheng Tao","Zongqi Wan","Qixin Zhang"],"reviews":0,"subject":"cs.DS","summary":"Over the past decade, a growing body of research has shown that $γ$-weak submodularity broadly arises in numerous subset selection tasks, including feature selection, neural network pruning, and video summarization. Despite its prevalence, maximizing a $γ$-weakly submodular function subject to a general matroid constraint remains challenging. To date, the only known approximation guarantee is the conservative $(1+1/γ)^{-2}$ factor established by \\citet{chen2018weakly}. To improve upon this result, this paper proposes a novel algorithm called \\MGPE, which repeatedly performs maximum-gain…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-21","reactions":{}}