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