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

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 citetchen2018weakly. To improve upon this result, this paper proposes a novel algorithm called MGPE, which repeatedly performs maximum-gain local exchanges through careful control of a non-homogeneous Poisson clock, and proves that this MGPE can attain an approximation ratio arbitrarily close to ργ=1-left(γ/(2-γ)right)^ fracγ22(1-γ) . In sharp contrast to the previous guarantee, our obtained factor ργ not only strictly improves upon (1+1/γ)-2 for every γ∈(0,1], but also can asymptotically approach the optimal (1-1/e)-approximation for submodular maximization as γ→1. Furthermore, we surprisingly find that when the matroid constraint reduces to a cardinality or the objective satisfies the stronger notion of α-weak DR-submodularity, MGPE can automatically recover the tight approximation ratios of 1-e-γ and 1-e-α, respectively. Here, α∈(0,1] denotes the DR ratio.