SOURCE-LINKED INTELLIGENCE

Poisson Exchange Beyond Submodularity: Effective Approximation Algorithms for Offline and Online Subset Selection over Matroids

arXiv · AI, language, vision and robotics · article · Sep 21, 2026 · UTC

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 local

Read original source ↗ Open in workspace

recordType

paper

region

Global