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

arXiv:2609.24569v2 Announce Type: replace-cross Abstract: Over the past decade, a growing body of research has shown that $\gamma$-weak submodularity broadly arises in numerous subset selection tasks, including feature selection, neural network pruning, and video summarization. Despite its prevalence, maximizing a $\gamma$-weakly submodular function subject to a general matroid constraint remains challenging. To date, the only known approximation guarantee is the conservative $(1+1/\gamma)^{-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 exchanges through careful control of a non-homogeneous Poisson clock, and proves that this \MGPE\ can attain an approximation ratio arbitrarily close to $\rho_\gamma=1-\left(\gamma/(2-\gamma)\right)^{ \frac{\gamma^2}{2(1-\gamma)} }$. In sharp contrast to the previous guarantee, our obtained factor $\rho_\gamma$ not only strictly improves upon $(1+1/\gamma)^{-2}$ for every $\gamma\in(0,1]$, but also can asymptotically approach the optimal $(1-1/e)$-approximation for submodular maximization as $\gamma\to1$. Furthermore, we surprisingly find that when the matroid constraint reduces to a cardinality or the objective satisfies the stronger notion of $\alpha$-weak DR-submodularity, \MGPE\ can automatically recover the tight approximation ratios of $1-e^{-\gamma}$ and $1-e^{-\alpha}$, respectively. Here, $\alpha\in(0,1]$ denotes the DR ratio.